QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190399#5479. Traveling Salesperson in an IslandGenshinImpactsFaultWA 11ms4220kbC++143.8kb2023-09-28 20:21:532023-09-28 20:21:54

Judging History

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

  • [2023-09-28 20:21:54]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:4220kb
  • [2023-09-28 20:21:53]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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'