QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#152255 | #5479. Traveling Salesperson in an Island | fhvirus | AC ✓ | 10ms | 4108kb | C++17 | 4.2kb | 2023-08-27 21:23:02 | 2023-08-27 21:23:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int) (x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef NONTOI
#define debug(args...) LKJ("\033[1;32m["#args"]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void print(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b], ++a; }
#else
#define debug(...) ((void)0)
#define print(...) ((void)0)
#endif
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template <class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0): x(x), y(y) {}
bool operator< (P p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator== (P p) const { return tie(x, y) == tie(p.x, p.y); }
bool operator!= (P p) const { return tie(x, y) != tie(p.x, p.y); }
P operator + (P p) const { return P(x + p.x, y + p.y); }
P operator - (P p) const { return P(x - p.x, y - p.y); }
P operator * (T d) const { return P(x * d, y * d); }
P operator / (T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x * x + y * y; }
double dist() const { return sqrt((double)dist2()); }
double angle() const { return atan2(y, x); }
P unit() const { return *this / dist(); }
P perp() const { return P(-y, x); }
P normal() const { return perp().unit(); }
P rotate(double a) const {
return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }
friend ostream& operator<< (ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
template <class P> bool onSegment(P s, P e, P p)
{ return p.cross(s, e) == 0 and (s - p).dot(e - p) <= 0; }
template <class P> bool onSegment_strict(P s, P e, P p)
{ return p.cross(s, e) == 0 and (s - p).dot(e - p) < 0; }
template <class P> bool segInter(P a, P b, P c, P d) {
auto oa = c.cross(d, a), ob = c.cross(d, b),
oc = a.cross(b, c), od = a.cross(b, d);
if (sgn(oa) * sgn(ob) < 0 and sgn(oc) * sgn(od) < 0)
return true;
return false;
}
int main() {
cin.tie(0) -> sync_with_stdio(0);
cin.exceptions(cin.failbit);
typedef Point<ll> P;
int n, m;
cin >> n >> m;
vector<P> ps(n), port(m);
for (auto &[x, y]: ps) cin >> x >> y;
for (auto &[x, y]: port) cin >> x >> y;
ps.push_back(ps[0]);
vi on_id(m);
rep (i, 0, m) rep (j, 0, n) {
if (onSegment(ps[j], ps[j+1], port[i])) {
on_id[i] = j;
break;
}
}
vi ord(m);
iota(all(ord), 0);
sort(all(ord), [&](int a, int b) {
if (on_id[a] != on_id[b]) return on_id[a] < on_id[b];
P c = ps[on_id[a]];
return (port[a] - c).dist2() < (port[b] - c).dist2();
});
ord.push_back(ord[0]);
auto ps2 = ps;
for (auto &p: ps2) p = p * 2;
auto inside = [&](P p) -> bool {
bool in = false;
P pp = p + P(10000, 1);
rep (i, 0, n) {
in ^= segInter(p, pp, ps2[i], ps2[i+1]);
if (onSegment(ps2[i], ps2[i+1], p)) return true;
}
return in;
};
int N = n + m;
const double INF = 1e18;
vector<vector<double>> dis(N, vector<double>(N, INF));
rep (i, 0, N) dis[i][i] = 0;
rep (i, 0, n) dis[i][(i+1)%n] = dis[(i+1)%n][i] = (ps[i] - ps[i+1]).dist();
const auto can_build = [&](P a, P b) {
rep (i, 0, n) if (segInter(a, b, ps[i], ps[i+1])) return false;
rep (i, 0, n) if (onSegment_strict(a, b, ps[i])) return false;
if (!inside(a + b)) return false;
debug(a, b, (a - b).dist());
return true;
};
vector<P> allp;
rep (i, 0, n) allp.push_back(ps[i]);
rep (j, 0, m) allp.push_back(port[j]);
rep (i, 0, N) rep(j, i+1, N)
if (can_build(allp[i], allp[j]))
dis[i][j] = dis[j][i] = (allp[i] - allp[j]).dist();
rep (k, 0, N) rep (i, 0, N) rep (j, 0, N)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
double ans = 0;
rep (i, 0, m)
ans += dis[ord[i]+n][ord[i+1]+n], debug(port[ord[i]], port[ord[i+1]], dis[ord[i]+n][ord[i+1]+n]);
cout << setprecision(12) << fixed;
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3760kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 1 2 2 1 0 1
output:
5.656854249492
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3760kb
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.649110640674
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
4 4 0 0 2 0 2 2 0 2 1 0 2 1 1 2 0 1
output:
5.656854249492
result:
ok found '5.6568542', expected '5.6568542', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3772kb
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.649110640674
result:
ok found '16.6491106', expected '16.6491106', error '0.0000000'
Test #5:
score: 0
Accepted
time: 6ms
memory: 4020kb
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.575113934887
result:
ok found '14645.5751139', expected '14645.5751139', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3812kb
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.165785521091
result:
ok found '4777.1657855', expected '4777.1657855', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3732kb
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.282270124808
result:
ok found '4834.2822701', expected '4834.2822701', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3900kb
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.782717236181
result:
ok found '7282.7827172', expected '7282.7827172', error '0.0000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 4020kb
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.917700563397
result:
ok found '11475.9177006', expected '11475.9177006', error '0.0000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3952kb
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.610282430273
result:
ok found '4388.6102824', expected '4388.6102824', error '0.0000000'
Test #11:
score: 0
Accepted
time: 5ms
memory: 4108kb
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.214012135664
result:
ok found '14624.2140121', expected '14624.2140121', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3892kb
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.458930503273
result:
ok found '9082.4589305', expected '9082.4589305', error '0.0000000'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3896kb
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.419788077407
result:
ok found '8037.4197881', expected '8037.4197881', error '0.0000000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 4092kb
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.622879114175
result:
ok found '9778.6228791', expected '9778.6228791', error '0.0000000'
Test #15:
score: 0
Accepted
time: 3ms
memory: 4088kb
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.682966097994
result:
ok found '272.6829661', expected '272.6829661', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3980kb
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.312482100799
result:
ok found '4350.3124821', expected '4350.3124821', error '0.0000000'
Test #17:
score: 0
Accepted
time: 9ms
memory: 3992kb
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:
13643.219434246974
result:
ok found '13643.2194342', expected '13643.2194342', error '0.0000000'
Test #18:
score: 0
Accepted
time: 10ms
memory: 3896kb
input:
100 100 392 309 465 178 169 139 181 324 24 246 14 35 331 68 62 121 513 49 573 74 924 0 936 190 619 134 514 167 415 123 525 175 662 156 470 363 464 258 430 309 428 341 365 335 81 441 160 509 132 483 434 346 463 342 249 447 368 434 374 396 613 475 270 679 476 580 329 708 457 677 386 711 296 719 443 72...
output:
13661.068637354054
result:
ok found '13661.0686374', expected '13661.0686374', error '0.0000000'
Test #19:
score: 0
Accepted
time: 3ms
memory: 3912kb
input:
100 17 432 86 458 141 463 236 514 285 511 229 624 547 696 432 641 289 533 219 641 109 601 237 675 227 826 236 748 132 871 183 791 108 532 86 678 30 896 63 907 138 782 490 866 217 663 520 615 707 731 923 740 554 789 549 763 631 754 687 916 809 872 704 861 714 795 670 806 536 901 693 880 514 990 68 98...
output:
8088.529821981247
result:
ok found '8088.5298220', expected '8088.5298220', error '0.0000000'
Test #20:
score: 0
Accepted
time: 6ms
memory: 3904kb
input:
100 99 691 62 648 102 452 103 430 136 796 88 765 94 435 181 329 210 312 544 231 221 289 559 215 491 203 202 196 676 140 702 193 847 223 745 271 794 700 784 483 823 480 833 424 795 397 845 204 906 791 957 772 799 774 706 589 726 663 753 525 767 585 715 505 763 550 715 751 682 909 401 712 451 540 583 ...
output:
12421.894727565059
result:
ok found '12421.8947276', expected '12421.8947276', error '0.0000000'
Test #21:
score: 0
Accepted
time: 5ms
memory: 4108kb
input:
100 61 125 74 103 477 268 243 138 799 108 948 230 695 306 716 286 819 257 735 224 743 252 778 250 901 224 931 291 889 359 702 333 962 378 635 311 459 298 183 301 119 286 99 223 68 178 108 130 63 551 21 696 39 989 128 728 211 879 117 973 130 635 70 733 100 801 146 600 111 575 36 467 139 365 82 324 16...
output:
13040.661814823949
result:
ok found '13040.6618148', expected '13040.6618148', error '0.0000000'
Test #22:
score: 0
Accepted
time: 3ms
memory: 3992kb
input:
100 19 725 925 897 875 863 577 741 505 801 800 733 498 687 568 613 538 675 420 668 508 693 270 830 162 646 80 608 103 701 208 649 208 586 121 322 542 394 145 233 578 175 443 129 457 278 706 419 409 387 485 407 507 432 377 493 324 658 211 235 794 177 708 171 867 174 585 74 466 272 404 275 303 291 234...
output:
8705.578062637916
result:
ok found '8705.5780626', expected '8705.5780626', error '0.0000000'
Test #23:
score: 0
Accepted
time: 3ms
memory: 3924kb
input:
100 23 143 875 336 965 391 903 439 844 389 609 429 729 447 722 533 624 439 862 418 918 576 603 809 961 812 802 732 650 581 573 609 478 866 475 866 379 842 386 780 393 667 346 680 457 610 383 528 360 501 410 558 255 647 214 550 279 555 337 599 327 560 335 801 165 774 316 866 40 309 108 434 111 633 15...
output:
9903.609793235453
result:
ok found '9903.6097932', expected '9903.6097932', error '0.0000000'
Test #24:
score: 0
Accepted
time: 3ms
memory: 3900kb
input:
100 13 783 789 401 921 304 926 474 887 349 855 285 781 523 776 603 379 629 635 705 142 832 117 329 61 221 34 592 251 462 324 568 549 439 775 249 777 282 788 232 939 750 973 743 974 0 952 11 132 17 675 38 4 83 483 61 378 85 547 11 707 71 922 90 540 122 863 283 720 374 697 395 728 431 728 488 611 181 ...
output:
10384.310585679767
result:
ok found '10384.3105857', expected '10384.3105857', error '0.0000000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
5 5 26 44 902 393 679 710 440 582 161 571 440 582 902 393 679 710 26 44 161 571
output:
2424.892853429933
result:
ok found '2424.8928534', expected '2424.8928534', error '0.0000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
7 13 775 631 552 356 966 631 995 809 701 917 574 893 558 867 566 880 574 893 848 863 966 631 558 867 701 917 799 881 995 809 552 356 775 631 946 827 750 899 897 845
output:
1824.999320910321
result:
ok found '1824.9993209', expected '1824.9993209', error '0.0000000'
Test #27:
score: 0
Accepted
time: 1ms
memory: 4004kb
input:
4 12 989 431 442 600 810 336 879 215 488 567 718 402 580 501 934 323 879 215 626 468 442 600 764 369 810 336 672 435 989 431 534 534
output:
1407.101195736835
result:
ok found '1407.1011957', expected '1407.1011957', error '0.0000000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
4 7 123 406 376 200 733 923 625 880 376 200 123 406 374 643 614 682 495 441 733 923 625 880
output:
1939.260849625203
result:
ok found '1939.2608496', expected '1939.2608496', error '0.0000000'
Test #29:
score: 0
Accepted
time: 1ms
memory: 4008kb
input:
8 12 297 476 486 975 47 134 447 365 892 300 992 929 553 496 885 321 47 134 486 975 714 326 625 339 892 300 803 313 553 496 885 321 447 365 536 352 992 929 297 476
output:
4630.806251984375
result:
ok found '4630.8062520', expected '4630.8062520', error '0.0000000'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
7 32 452 490 299 670 767 137 910 364 573 727 133 686 25 716 97 696 551 383 910 364 515 424 479 465 367 590 659 260 587 342 371 588 25 716 61 706 731 178 79 701 133 686 767 137 401 550 350 610 623 301 452 490 573 727 443 506 316 650 407 547 43 711 299 670 435 510 384 570 695 219 333 630 115 691 335 6...
output:
2746.262511457468
result:
ok found '2746.2625115', expected '2746.2625115', error '0.0000000'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
6 5 526 122 868 126 669 561 500 435 507 543 319 867 460 624 319 867 413 705 526 122 366 786
output:
1560.488015654532
result:
ok found '1560.4880157', expected '1560.4880157', error '0.0000000'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
4 4 257 112 414 143 807 402 409 675 807 402 414 143 409 675 257 112
output:
1696.490094924265
result:
ok found '1696.4900949', expected '1696.4900949', error '0.0000000'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
5 78 500 641 677 523 931 817 337 823 706 769 599 575 662 533 617 563 626 557 634 820 608 569 629 555 506 637 593 579 460 805 542 793 578 589 530 621 503 639 603 705 560 601 804 670 575 591 832 818 638 549 512 633 623 559 602 573 545 611 611 567 671 527 518 629 563 599 931 817 566 597 656 537 596 577...
output:
1810.741882203966
result:
ok found '1810.7418822', expected '1810.7418822', error '0.0000000'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
7 10 542 424 980 989 447 978 458 936 502 560 38 345 975 126 458 936 469 842 542 424 480 748 980 989 447 978 502 560 975 126 38 345 491 654
output:
3669.266308795628
result:
ok found '3669.2663088', expected '3669.2663088', error '0.0000000'