ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#164580 | #2907. moon | anti | 100 | 606ms | 1204kb | C++11 | 1.4kb | 2022-11-05 09:22:51 | 2022-11-05 13:01:07 |
answer
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,n) for (int i=(a);i<=(n);i++)
#define per(i,a,n) for (int i=(n);i>=(a);i--)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define lowbit(i) ((i)&(-i))
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
using namespace std;
const int N = 1145;
int n, q, x[N], y[N];
int main() {
scanf("%d%d", &n, &q);
rep(i, 1, n) scanf("%d%d", &x[i], &y[i]);
rep(_, 1, q) {
int sx, sy, tx, ty, ans = inf;
scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
// (sx, sy) - (tx, sy) - (tx, ty)
rep(i, 1, n) {
for (pii o : {mp(sx, sy), mp(tx, sy), mp(tx, ty)}) {
int rad = (int) ceil(hypot(abs(x[i] - o.fi), abs(y[i] - o.se))),
tim = abs(sx - o.fi) + abs(sy - o.se);
ans = min(ans, rad - tim - 2);
}
{
int l = min(sx, tx), r = max(sx, tx);
if (l < x[i] && x[i] < r) { // (x[i], sy)
int rad = abs(y[i] - sy),
tim = abs(sx - x[i]);
ans = min(ans, rad - tim - 2);
}
}
{
int l = min(sy, ty), r = max(sy, ty);
if (l < y[i] && y[i] < r) { // (tx, y[i])
int rad = abs(x[i] - tx),
tim = abs(sx - tx) + abs(sy - y[i]);
ans = min(ans, rad - tim - 2);
}
}
}
printf("%d\n", max(-1, ans));
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 43ms
memory: 1204kb
input:
1000 1000 0 212333 0 283947 0 419206 0 700211 0 704012 0 603222 0 346328 0 779005 0 124972 0 861984 ...
output:
-1 -1 605 732 334 271 -1 -1 -1 -1 195 -1 606 -1 -1 -1 -1 166 -1 276 148 -1 278 -1 -1 113 -1 -1 -1 20...
result:
ok 1000 lines
Test #2:
score: 10
Accepted
time: 43ms
memory: 1204kb
input:
1000 1000 0 662423 0 606008 0 791196 0 242205 0 217045 0 457311 0 717943 0 858612 0 73523 0 101532 0...
output:
316 -1 -1 458 783 -1 632 -1 1163 164 -1 -1 -1 617 0 -1 -1 -1 47 399 210 481 -1 220 544 -1 64 -1 -1 2...
result:
ok 1000 lines
Test #3:
score: 10
Accepted
time: 43ms
memory: 1204kb
input:
1000 1000 0 828144 0 276070 0 984925 0 229830 0 40474 0 96831 0 146398 0 272704 0 264943 0 147051 0 ...
output:
21 -1 686 -1 -1 -1 92 -1 484 -1 -1 84 -1 -1 -1 -1 1034 -1 -1 -1 -1 -1 309 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok 1000 lines
Test #4:
score: 10
Accepted
time: 44ms
memory: 1204kb
input:
1000 1000 0 341547 0 606717 0 79249 0 603397 0 777363 0 956846 0 965646 0 249422 0 583457 0 873475 0...
output:
-1 1361 767 -1 -1 -1 -1 555 761 575 699 -1 -1 -1 -1 -1 565 -1 579 111 572 -1 1121 -1 -1 780 422 230 ...
result:
ok 1000 lines
Test #5:
score: 10
Accepted
time: 43ms
memory: 1200kb
input:
1000 1000 0 855912 0 760201 0 858056 0 836272 0 788744 0 994911 0 142988 0 467354 0 98575 0 635616 0...
output:
462 -1 113 -1 307 240 1498 953 -1 261 -1 288 1626 -1 75 38 -1 3521 737 121 -1 -1 -1 -1 1763 -1 -1 -1...
result:
ok 1000 lines
Test #6:
score: 10
Accepted
time: 77ms
memory: 1200kb
input:
1000 1000 381669 925292 514002 408344 412172 775834 879004 724399 81283 599326 982979 936347 513029 ...
output:
5267 32709 3218 19345 15684 5210 916 2554 4505 5362 800 464 2452 9433 747 7948 24534 10413 3406 7039...
result:
ok 1000 lines
Test #7:
score: 10
Accepted
time: 74ms
memory: 1200kb
input:
1000 1000 543803 844263 856944 503751 884464 629593 642723 534256 727730 875569 155824 514857 551581...
output:
393 31199 681 2712 19168 1316 21359 7302 26287 28057 917 571 3807 16781 21121 2338 12342 1196 3933 1...
result:
ok 1000 lines
Test #8:
score: 10
Accepted
time: 86ms
memory: 1200kb
input:
1000 1000 610538 921200 825059 254693 742633 941338 511931 636739 395274 972716 695703 722727 518638...
output:
7661 24565 5018 10129 93 6148 24921 9380 915 8156 1676 2582 1836 7197 20354 879 1258 4671 9851 1396 ...
result:
ok 1000 lines
Test #9:
score: 10
Accepted
time: 76ms
memory: 1200kb
input:
1000 1000 510034 707043 347191 923962 910156 293115 759134 788880 815658 926241 889893 191765 915064...
output:
9021 20111 6902 5606 4996 18399 17267 5366 3080 16633 14831 81077 146 7110 50517 5031 10417 23747 -1...
result:
ok 1000 lines
Test #10:
score: 10
Accepted
time: 77ms
memory: 1200kb
input:
1000 1000 791074 773488 651651 784700 963407 913302 652959 857044 331287 754286 348852 470019 935094...
output:
8662 24748 7736 55328 11791 2676 13210 5679 2995 7172 45289 1839 4255 156 7512 1189 4306 1604 10717 ...
result:
ok 1000 lines