QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#152255#5479. Traveling Salesperson in an IslandfhvirusAC ✓10ms4108kbC++174.2kb2023-08-27 21:23:022023-08-27 21:23:02

Judging History

你现在查看的是最新测评结果

  • [2023-08-27 21:23:02]
  • 评测
  • 测评结果:AC
  • 用时:10ms
  • 内存:4108kb
  • [2023-08-27 21:23:02]
  • 提交

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'