QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#262868#5479. Traveling Salesperson in an Islandxaphoenix#AC ✓568ms4684kbC++175.0kb2023-11-24 09:40:142023-11-24 09:40:14

Judging History

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

  • [2023-11-24 09:40:14]
  • 评测
  • 测评结果:AC
  • 用时:568ms
  • 内存:4684kb
  • [2023-11-24 09:40:14]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repn(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = (n) - 1; i >= a; i--)
#define pern(i, a, n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;

const int N = 210;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;

mt19937_64 Rand((unsigned long long)new char);
#define rand Rand

int n, m;
const double eps = 1e-10, pi = acos(-1.0);
inline int dcmp(LD x) {
    return (x > eps) - (x < -eps);
}
LD dis[N][N];
struct Point {
    LD x, y;
    int id;
    LD d;
    Point (double x = 0 , double y = 0) : x(x) , y(y) {}
    void input() {
        cin >> x >> y;
    }
    bool operator < (const Point& R) const {
        if (dcmp(x - R.x) == 0)
            return dcmp(y - R.y) < 0;
        return dcmp(x - R.x) < 0;
    }
    bool operator == (const Point& R) const {
        return dcmp(x - R.x) == 0 && dcmp(y - R.y) == 0;
    }
    Point operator + (const Point& R) const {
        return Point(x + R.x, y + R.y);
    }
    Point operator - (const Point& R) const {
        return Point(x - R.x, y - R.y);
    }
    Point operator * (const double& R) const {
        return Point(x * R, y * R);
    }
    Point operator / (const double& R) const {
        return Point(x / R, y / R);
    }
    LD operator ^ (const Point& R) const {
        return x * R.y - y * R.x;
    }
    LD operator % (const Point& R) const {
        return x * R.x + y * R.y;
    }
    LD len() {
        return sqrt(*this % *this);
    }
    double angle() {
        return atan2(y, x);
    }
}p[N], poly[N];
Point GetLineIntersection(Point P, Point v, Point Q, Point w) {
    Point u = P - Q;
    LD t1 = (w ^ u) / (v ^ w);
    return P + v * t1;
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2) {
    LD c1 = (a2 - a1) ^ (b1 - a1);
    LD c2 = (a2 - a1) ^ (b2 - a1);
    if (dcmp(c1) == 0 && dcmp(c2) == 0) {
        if (a2 < a1) swap(a1 , a2);
        if (b2 < b1) swap(b1 , b2);
        return max(a1 , b1) < min(a2 , b2);
    }
    LD c3 = (b2 - b1) ^ (a1 - b1);
    LD c4 = (b2 - b1) ^ (a2 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

bool OnSegment(Point P, Point a1, Point a2) {
    LD len = (P - a1).len();
    if (dcmp(len) == 0) return true;
    a1 = a1 - P , a2 = a2 - P;
    return dcmp((a1 ^ a2) / len) == 0 && dcmp(a1 % a2) <= 0;
}
bool SegmentIntersection(Point a1, Point a2, Point b1, Point b2) {
    if (OnSegment(a1, b1, b2)) return true;
    if (OnSegment(a2, b1, b2)) return true;
    if (OnSegment(b1, a1, a2)) return true;
    if (OnSegment(b2, a1, a2)) return true;
    return SegmentProperIntersection(a1, a2, b1, b2);
}
int cmp(Point a, Point b) {
	if (a.id != b.id) return a.id < b.id;
	return a.d < b.d;
}
bool pointInPolygon(Point P , Point *p , int n) {
    for (int i = 0 ; i < n ; ++ i)
        if (OnSegment(P , p[i] , p[i + 1]))
            return 1;
    int res = 0;
    for (int i = 0 ; i < n ; ++ i) {
        Point a = p[i] , b = p[i + 1];
        if (a.y > b.y) swap(a , b);
        if (dcmp((a - P) ^ (b - P)) < 0 && dcmp(a.y - P.y) < 0 && dcmp(b.y - P.y) >= 0)
            res ^= 1;
    }
    return res;
}
int main() {
	IO;
	cin >> n >> m;
	repn(i, 1, n + m) p[i].input();
	rep(i, 0, n) poly[i] = p[i + 1];
	poly[n] = p[1];
	repn(i, n + 1, n + m) {
		repn(j, 1, n) {
			Point x = p[j], y;
			if (j == n) y = p[1];
			else y = p[j + 1];
			if (!(p[i] == y) && OnSegment(p[i], x, y)) {
				p[i].id = j;
				p[i].d = (p[i] - x).len();
				break;
			}
		}
	}
	sort(p + n + 1, p + n + m + 1, cmp);
	repn(i, 1, n + m) repn(j, 1, n + m) {
		dis[i][j] = INF;
		Point x = p[i], y = p[j];
		vector<Point> v;
		v.pb(x), v.pb(y);
		repn(k, 1, n) {
			Point a = p[k], b;
			if (k == n) b = p[1];
			else b = p[k + 1];
			if (SegmentIntersection(x, y, a, b)) {
				Point z = GetLineIntersection(x, y - x, a, b - a);
				v.pb(z);
			}
		}
		sort(all(v));
		int flag = 0;
		rep(i, 1, SZ(v)) {
			if (v[i - 1] == v[i]) continue;
			Point c = (v[i - 1] + v[i]) / 2;
			if (!pointInPolygon(c, poly, n)) {
				flag = 1;
				break;
			}
		}
		if (!flag) dis[i][j] = (p[i] - p[j]).len();
	}
	repn(k, 1, n + m) repn(i, 1, n + m) repn(j, 1, n + m) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	double ans = 0;
	repn(i, n + 2, n + m) ans += dis[i - 1][i];
	ans += dis[n + m][n + 1];
	cout << fixed << setprecision(15) << ans << "\n";
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4104kb

input:

4 4
0 0
2 0
2 2
0 2
1 0
1 2
2 1
0 1

output:

5.656854249492381

result:

ok found '5.6568542', expected '5.6568542', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3932kb

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.649110640673516

result:

ok found '16.6491106', expected '16.6491106', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

4 4
0 0
2 0
2 2
0 2
1 0
2 1
1 2
0 1

output:

5.656854249492381

result:

ok found '5.6568542', expected '5.6568542', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 4092kb

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.649110640673516

result:

ok found '16.6491106', expected '16.6491106', error '0.0000000'

Test #5:

score: 0
Accepted
time: 328ms
memory: 4352kb

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.575113934890396

result:

ok found '14645.5751139', expected '14645.5751139', error '0.0000000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 4044kb

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.165785521091493

result:

ok found '4777.1657855', expected '4777.1657855', error '0.0000000'

Test #7:

score: 0
Accepted
time: 8ms
memory: 4044kb

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.282270124807837

result:

ok found '4834.2822701', expected '4834.2822701', error '0.0000000'

Test #8:

score: 0
Accepted
time: 81ms
memory: 4264kb

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.782717236181270

result:

ok found '7282.7827172', expected '7282.7827172', error '0.0000000'

Test #9:

score: 0
Accepted
time: 84ms
memory: 4132kb

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.917700563397375

result:

ok found '11475.9177006', expected '11475.9177006', error '0.0000000'

Test #10:

score: 0
Accepted
time: 41ms
memory: 4204kb

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.610282430260668

result:

ok found '4388.6102824', expected '4388.6102824', error '0.0000000'

Test #11:

score: 0
Accepted
time: 233ms
memory: 4432kb

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.214012135660596

result:

ok found '14624.2140121', expected '14624.2140121', error '0.0000000'

Test #12:

score: 0
Accepted
time: 80ms
memory: 4336kb

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.458930503275042

result:

ok found '9082.4589305', expected '9082.4589305', error '0.0000000'

Test #13:

score: 0
Accepted
time: 81ms
memory: 4308kb

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.419788077402700

result:

ok found '8037.4197881', expected '8037.4197881', error '0.0000000'

Test #14:

score: 0
Accepted
time: 104ms
memory: 4164kb

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.622879114176612

result:

ok found '9778.6228791', expected '9778.6228791', error '0.0000000'

Test #15:

score: 0
Accepted
time: 144ms
memory: 4224kb

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.682966097994495

result:

ok found '272.6829661', expected '272.6829661', error '0.0000000'

Test #16:

score: 0
Accepted
time: 144ms
memory: 4168kb

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.312482100798661

result:

ok found '4350.3124821', expected '4350.3124821', error '0.0000000'

Test #17:

score: 0
Accepted
time: 568ms
memory: 4684kb

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.219434246979290

result:

ok found '13643.2194342', expected '13643.2194342', error '0.0000000'

Test #18:

score: 0
Accepted
time: 568ms
memory: 4560kb

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.068637354053863

result:

ok found '13661.0686374', expected '13661.0686374', error '0.0000000'

Test #19:

score: 0
Accepted
time: 188ms
memory: 4176kb

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.529821981246641

result:

ok found '8088.5298220', expected '8088.5298220', error '0.0000000'

Test #20:

score: 0
Accepted
time: 562ms
memory: 4556kb

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.894727565060748

result:

ok found '12421.8947276', expected '12421.8947276', error '0.0000000'

Test #21:

score: 0
Accepted
time: 365ms
memory: 4608kb

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.661814823948589

result:

ok found '13040.6618148', expected '13040.6618148', error '0.0000000'

Test #22:

score: 0
Accepted
time: 197ms
memory: 4456kb

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.578062637916446

result:

ok found '8705.5780626', expected '8705.5780626', error '0.0000000'

Test #23:

score: 0
Accepted
time: 208ms
memory: 4260kb

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.609793235453253

result:

ok found '9903.6097932', expected '9903.6097932', error '0.0000000'

Test #24:

score: 0
Accepted
time: 175ms
memory: 4160kb

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.310585679766518

result:

ok found '10384.3105857', expected '10384.3105857', error '0.0000000'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3868kb

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.892853429932529

result:

ok found '2424.8928534', expected '2424.8928534', error '0.0000000'

Test #26:

score: 0
Accepted
time: 0ms
memory: 4140kb

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.999320910320648

result:

ok found '1824.9993209', expected '1824.9993209', error '0.0000000'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3948kb

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.101195736834825

result:

ok found '1407.1011957', expected '1407.1011957', error '0.0000000'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3936kb

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.260849625203036

result:

ok found '1939.2608496', expected '1939.2608496', error '0.0000000'

Test #29:

score: 0
Accepted
time: 1ms
memory: 4004kb

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.806251984374285

result:

ok found '4630.8062520', expected '4630.8062520', error '0.0000000'

Test #30:

score: 0
Accepted
time: 4ms
memory: 4024kb

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.262511457466189

result:

ok found '2746.2625115', expected '2746.2625115', error '0.0000000'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3932kb

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.488015654531637

result:

ok found '1560.4880157', expected '1560.4880157', error '0.0000000'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

4 4
257 112
414 143
807 402
409 675
807 402
414 143
409 675
257 112

output:

1696.490094924265122

result:

ok found '1696.4900949', expected '1696.4900949', error '0.0000000'

Test #33:

score: 0
Accepted
time: 18ms
memory: 4232kb

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.741882203965361

result:

ok found '1810.7418822', expected '1810.7418822', error '0.0000000'

Test #34:

score: 0
Accepted
time: 1ms
memory: 4056kb

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.266308795628447

result:

ok found '3669.2663088', expected '3669.2663088', error '0.0000000'