QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#190399 | #5479. Traveling Salesperson in an Island | GenshinImpactsFault | WA | 11ms | 4220kb | C++14 | 3.8kb | 2023-09-28 20:21:53 | 2023-09-28 20:21:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n, m;
double dis[N][N];
struct P {
int x, y;
P(int X = 0, int Y = 0) : x(X), y(Y) {}
inline P operator+(const P &yy)const { return P(x + yy.x, y + yy.y); }
inline P operator-(const P &yy)const { return P(x - yy.x, y - yy.y); }
inline int operator&(const P &yy)const { return 1ll * x * yy.x + 1ll * y * yy.y; }
inline int operator*(const P &yy)const { return 1ll * x * yy.y - 1ll * y * yy.x; }
inline bool operator==(const P &yy)const { return x == yy.x && y == yy.y; }
inline bool operator!=(const P &yy)const { return !(P(x, y) == yy); }
double len() {
return sqrt(1.0 * x * x + 1.0 * y * y);
}
}; P a[N], b[N], c[N];
int id[N];
double d[N];
bool inside(P l, P r, P x) {
if((r - l) * (x - l)) return 0;
if(((l - x) & (r - x)) > 0) return 0;
return 1;
}
bool inang(P l, P r, P x) {
if(l * r > 0) {
return l * x > 0 && x * r > 0;
}
else {
return !(r * x >= 0 && x * l >= 0);
}
}
bool cross(P l, P r, P x, P y) {
int w1 = (x - l) * (y - l);
int w2 = (x - r) * (y - r);
int w3 = (l - x) * (r - x);
int w4 = (l - y) * (r - y);
if(w1 && w2 && w3 && w4 && (w1 > 0) != (w2 > 0) && (w3 > 0) != (w4 > 0))
return 1;
return 0;
}
double calc_dis(P x) {
double res = 0;
for(int i = 0; i < n; i++) {
P l = a[i], r = a[(i + 1) % n];
if(inside(l, r, x)) {
res += (x - l).len();
break;
}
res += (r - l).len();
}
return res;
}
bool check(int u, int v) {
P x = c[u], y = c[v];
if(x == y) return 1;
for(int i = 0; i < n; i++) {
P l = a[i], r = a[(i + 1) % n];
int w1 = (x - l) * (y - l);
int w2 = (x - r) * (y - r);
int w3 = (l - x) * (r - x);
int w4 = (l - y) * (r - y);
if(w1 && w2 && w3 && w4 && (w1 > 0) != (w2 > 0) && (w3 > 0) != (w4 > 0))
return 0;
if(w1 == 0 || w2 == 0) continue;
if(w3 == 0) {
// x
if((r - l) * (y - x) < 0) return 0;
}
if(w4 == 0) {
// y
if((r - l) * (x - y) < 0) return 0;
}
}
for(int i = 0; i < n; i++) {
if(cross(a[(i + 1) % n], a[i], x, y)) return 0;
if(inside(x, y, a[i])) {
P l = a[(i + n - 1) % n] - a[i];
P r = a[(i + 1) % n] - a[i];
if(!(x == a[i]) && inang(l, r, x - a[i])) return 0;
if(!(y == a[i]) && inang(l, r, y - a[i])) return 0;
}
else {
P p = a[i], q = a[(i + 1) % n];
if(x != p && x != q && inside(a[i], q, x) && (q - p) * (y - x) < 0)
return 0;
if(y != p && y != q && inside(a[i], q, y) && (q - p) * (x - y) < 0)
return 0;
}
}
return 1;
}
int main() {
ios::sync_with_stdio(0); cin.tie(nullptr);
cout << fixed << setprecision(11);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i - 1].x >> a[i - 1].y;
}
for(int i = 1; i <= m; i++) {
cin >> b[i].x >> b[i].y;
id[i] = i;
d[i] = calc_dis(b[i]);
}
sort(id + 1, id + m + 1, [](int x, int y) { return d[x] < d[y]; });
for(int i = 1; i <= m; i++) c[i] = b[id[i]];
swap(b, c);
for(int i = 1; i <= n; i++) c[i] = a[i - 1];
for(int i = 1; i <= m; i++) c[i + n] = b[i];
for(int i = 1; i <= n + m; i++)
for(int j = i + 1; j <= n + m; j++) {
dis[i][j] = dis[j][i] = 1e9;
if(check(i, j)) {
dis[i][j] = dis[j][i] = (c[i] - c[j]).len();
// cout << ">>> " << i << " " << j << " : " << c[i].x << " " << c[i].y << " -> " << c[j].x << " " << c[j].y << "\n";
}
}
for(int i = 1; i <= n; i++)
dis[i][i % n + 1] = dis[i % n + 1][i] = (c[i] - c[i % n + 1]).len();
for(int k = 1; k <= n + m; k++)
for(int i = 1; i <= n + m; i++)
for(int j = 1; j <= n + m; j++)
if(dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
double ans = 0;
for(int i = 1; i <= m; i++) {
ans += dis[n + i][n + i % m + 1];
}
cout << ans << "\n";
return 0;
}
// 7 2
// 0 0
// 4 0
// 4 4
// 0 4
// 0 3
// 3 3
// 0 1
// 0 0
// 0 4
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3848kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 1 2 2 1 0 1
output:
5.65685424949
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
8 2 0 0 4 0 4 4 0 4 0 3 3 3 3 1 0 1 0 0 0 4
output:
16.64911064067
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 2 1 1 2 0 1
output:
5.65685424949
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
8 2 0 0 4 0 4 4 0 4 0 3 3 3 3 1 0 1 0 0 0 4
output:
16.64911064067
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #5:
score: 0
Accepted
time: 7ms
memory: 4184kb
input:
76 98 268 97 299 202 133 205 110 251 384 226 332 198 532 241 448 83 268 82 543 62 873 93 387 317 905 90 945 132 827 335 983 222 919 534 945 264 910 287 789 705 837 176 793 563 777 665 782 345 746 315 715 315 810 161 369 599 278 671 641 423 703 344 753 619 672 402 596 709 161 701 216 857 325 942 135 ...
output:
14645.57511393489
result:
ok found '14645.5751139', expected '14645.5751139', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
13 31 513 619 610 142 875 42 946 259 778 746 982 181 829 896 759 944 654 960 815 526 484 632 533 870 253 557 794 920 716 102 663 122 829 896 875 42 982 181 700 836 533 870 610 142 778 746 513 619 677 898 822 62 512 768 769 82 792 588 498 700 526 836 723 774 946 259 769 650 505 734 815 526 759 944 51...
output:
4777.16578552109
result:
ok found '4777.1657855', expected '4777.1657855', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
27 16 119 437 377 849 332 666 501 726 184 491 455 630 410 348 248 90 543 282 662 399 455 133 613 264 760 337 963 48 854 260 698 579 585 334 451 324 950 897 554 623 660 777 987 969 255 986 524 927 135 956 341 896 95 855 425 442 455 133 524 927 155 865 356 262 173 868 585 334 197 872 662 399 263 883 2...
output:
4834.28227012481
result:
ok found '4834.2822701', expected '4834.2822701', error '0.0000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3932kb
input:
74 14 286 717 273 773 480 817 594 766 455 893 308 823 360 854 20 800 27 683 14 308 22 44 60 358 61 311 46 71 356 91 261 239 195 203 134 615 216 591 171 516 194 386 378 98 235 36 463 76 526 192 668 59 258 3 541 39 769 64 680 45 938 28 984 41 944 148 891 553 900 190 856 552 957 586 996 716 896 811 830...
output:
7282.78271723618
result:
ok found '7282.7827172', expected '7282.7827172', error '0.0000000'
Test #9:
score: 0
Accepted
time: 3ms
memory: 3988kb
input:
49 58 929 978 899 687 934 994 771 914 558 759 288 870 499 888 276 884 740 968 210 915 156 947 102 877 16 981 80 165 88 122 104 378 145 42 691 31 357 161 706 62 283 204 649 298 538 174 725 333 427 295 916 532 778 212 992 70 978 707 840 656 163 309 259 626 245 503 318 517 277 439 812 656 647 595 241 6...
output:
11475.91770056340
result:
ok found '11475.9177006', expected '11475.9177006', error '0.0000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3992kb
input:
15 95 383 952 222 802 62 950 183 745 75 827 488 290 311 243 206 250 197 541 133 285 357 38 778 314 982 497 748 377 456 805 154 369 177 461 787 397 142 876 142 321 865 437 529 698 145 333 488 290 155 373 982 497 136 297 846 375 180 473 133 285 165 413 197 541 158 385 174 449 383 952 138 305 187 501 1...
output:
4388.61028243027
result:
ok found '4388.6102824', expected '4388.6102824', error '0.0000000'
Test #11:
score: 0
Accepted
time: 3ms
memory: 4100kb
input:
61 100 235 140 360 187 608 102 289 103 332 143 83 58 272 31 503 57 824 109 360 911 716 414 772 413 840 478 777 254 795 174 896 557 834 280 937 195 945 413 985 863 824 974 330 978 690 534 475 912 681 576 702 738 574 928 926 732 697 514 361 912 169 757 219 883 160 942 84 652 174 690 48 71 139 337 176 ...
output:
14624.21401213566
result:
ok found '14624.2140121', expected '14624.2140121', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3928kb
input:
44 67 416 433 523 294 265 404 321 271 469 232 683 215 395 153 179 163 459 42 579 90 628 4 833 124 664 298 972 180 978 654 733 331 648 546 368 587 423 702 868 619 952 735 942 714 994 794 821 988 965 760 467 920 556 859 331 909 118 929 527 816 31 839 56 93 223 222 456 224 112 336 98 303 81 399 129 462...
output:
9082.45893050327
result:
ok found '9082.4589305', expected '9082.4589305', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
34 89 632 703 569 342 867 361 911 361 365 252 364 114 640 62 514 184 698 151 676 278 707 125 860 74 966 384 998 883 787 633 709 393 668 812 794 834 305 988 237 919 161 595 71 774 47 118 441 735 310 625 217 809 266 795 304 710 404 720 406 797 548 638 384 569 192 271 432 436 53 282 752 110 65 610 884 ...
output:
8037.41978807741
result:
ok found '8037.4197881', expected '8037.4197881', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
73 28 345 595 330 439 283 615 363 752 404 748 318 909 387 885 380 793 569 933 692 858 732 761 834 842 699 487 704 373 720 458 829 656 771 541 713 386 954 893 843 659 836 306 693 343 681 816 533 712 465 758 507 654 454 500 814 101 907 40 736 150 721 21 724 18 57 97 819 1 930 31 908 100 950 735 928 47...
output:
9778.62287911417
result:
ok found '9778.6228791', expected '9778.6228791', error '0.0000000'
Test #15:
score: 0
Accepted
time: 3ms
memory: 4080kb
input:
100 2 937 824 638 992 774 894 765 906 874 823 695 935 446 897 594 932 632 966 277 915 78 920 418 971 596 972 316 974 26 933 49 829 151 714 231 727 504 630 640 605 715 424 527 485 861 260 730 317 744 230 786 169 663 196 608 251 377 220 530 206 471 173 662 107 706 166 762 168 690 69 288 132 154 244 21...
output:
272.68296609799
result:
ok found '272.6829661', expected '272.6829661', error '0.0000000'
Test #16:
score: 0
Accepted
time: 3ms
memory: 4076kb
input:
100 2 644 654 839 510 852 468 826 780 841 772 771 826 819 689 701 846 876 838 814 848 774 845 918 903 668 926 739 965 516 974 868 969 767 988 253 989 257 963 169 992 283 931 708 904 614 777 446 736 315 777 447 145 261 77 298 505 265 601 367 453 235 874 325 568 218 857 247 452 161 633 144 541 125 582...
output:
4350.31248210080
result:
ok found '4350.3124821', expected '4350.3124821', error '0.0000000'
Test #17:
score: -100
Wrong Answer
time: 11ms
memory: 4220kb
input:
100 100 599 321 824 611 842 584 812 702 902 822 970 574 995 480 985 670 943 807 972 645 917 897 744 959 860 883 799 787 870 806 559 374 522 321 660 588 655 644 759 730 614 672 620 686 629 914 591 885 620 786 497 878 551 794 540 601 489 796 450 992 108 956 272 893 504 645 510 578 456 666 470 365 429 ...
output:
13653.98976386124
result:
wrong answer 1st numbers differ - expected: '13643.2194342', found: '13653.9897639', error = '0.0007894'