QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168788#6639. Disk Treeucup-team1209WA 423ms35176kbC++202.0kb2023-09-08 22:00:332023-09-08 22:00:34

Judging History

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

  • [2023-09-08 22:00:34]
  • 评测
  • 测评结果:WA
  • 用时:423ms
  • 内存:35176kb
  • [2023-09-08 22:00:33]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 200005;


using db = double;
using cp = std::complex<db>;
const db pi = std::acos(-1);

std::mt19937 gen(time(0) + (size_t) new char);
int n;
cp a[N], b[N];
int r[N], id0[N], id1[N];
int pos[N];
struct edge { int u, v; db w; };
std::vector<edge> e;
int anc[N];
db dist(int x, int y) { return abs(a[x] - a[y]) - r[x] - r[y]; }
struct pr {
	db w; int id;
} bit[N];
int find(int x) {
	return anc[x] == x ? x : anc[x] = find(anc[x]);
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for(int i = 0;i < n;++i) {
		int x, y; cin >> x >> y >> r[i];
		a[i] = cp(x, y);
		id0[i] = i;
		id1[i] = i;
		anc[i] = i;
	}
	for(db arg : {0., 0.25, 0.5, 0.75}) {
		cp r = std::polar(1., arg * pi * 2);
		for(int i = 0;i < n;++i) b[i] = a[i] * r;
		std::sort(id0, id0 + n, [](int x, int y) { return b[x].real() < b[y].real(); });
		std::sort(id1, id1 + n, [](int x, int y) { return b[x].imag() < b[y].imag(); });
		for(int j = 0;j < n;++j) {
			pos[id1[j]] = j + 1;
		}
		for(int i = 1;i <= n;++i) {
			bit[i] = {5e9, -1};
		}
		for(int i = n - 1;i >= 0;--i) {
			int x = id0[i];

			int id = -1;
			db dx = 5e9;

			for(int i = pos[x];i <= n;i += i & -i) {
				int t = bit[i].id;
				if(t != -1) {
					db dd = dist(t, x);
					if(id == -1) {
						id = t;
						dx = dd;
					} else {
						if(dd < dx) {
							dx = dd;
							id = t;
						}
					}
				}
			}

			pr z = { b[x].real() + b[x].imag() - ::r[x], x};
			for(int i = pos[x];i;i &= i - 1) {
				if(z.w < bit[i].w) bit[i] = z;
			}
			if(id >= 0) {
				e.push_back({x, id, dx});
			}
		}
	}
	sort(e.begin(), e.end(), [](edge x, edge y) { return x.w < y.w; });
	cout << "YES" << '\n';
	for(auto [u, v, w] : e) {
		if(find(u) != find(v)) {
			cout << (int) a[u].real() << ' ' << (int) a[u].imag() << ' ';
			cout << (int) a[v].real() << ' ' << (int) a[v].imag() << '\n';
			anc[find(u)] = find(v);
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 10048kb

input:

3
1 0 3
10 10 6
0 5 1

output:

YES
0 5 1 0
0 5 10 10

result:

ok answer = 1

Test #2:

score: 0
Accepted
time: 3ms
memory: 12192kb

input:

2
1 1 1
3 3 1

output:

YES
1 1 3 3

result:

ok answer = 1

Test #3:

score: 0
Accepted
time: 3ms
memory: 10144kb

input:

5
10 10 10
2 0 1
20 20 1
3 20 1
20 0 1

output:

YES
3 20 10 10
2 0 10 10
10 10 20 20
10 10 20 0

result:

ok answer = 1

Test #4:

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

input:

10
29 29 2
28 55 10
99 81 4
17 82 10
45 88 10
48 68 10
0 8 10
98 95 10
34 0 10
17 24 10

output:

YES
99 81 98 95
48 68 45 88
17 24 29 29
0 8 17 24
28 55 48 68
17 82 45 88
34 0 17 24
28 55 17 24
98 95 45 88

result:

ok answer = 1

Test #5:

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

input:

100
490 783 12
666 460 55
561 245 6
223 323 25
3 520 77
225 161 24
514 190 16
997 914 100
412 265 100
374 610 36
296 854 39
601 901 2
307 21 100
390 422 24
940 414 32
332 438 35
553 992 100
235 775 3
656 901 37
770 417 22
649 305 100
448 84 3
375 939 77
910 847 9
776 357 37
743 97 100
371 502 39
508...

output:

YES
649 305 560 422
375 939 468 868
743 97 742 210
92 366 204 512
447 40 448 84
307 21 205 100
964 284 837 286
811 693 809 794
375 939 293 965
981 11 865 52
375 939 296 854
304 613 374 610
160 703 252 629
445 639 563 635
964 284 899 204
160 703 119 603
508 524 458 464
116 850 67 952
95 208 76 226
13...

result:

ok answer = 1

Test #6:

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

input:

200
2948 9798 687
3897 647 35
3918 587 28
1262 2717 206
1315 9524 20
2381 305 1000
4344 6858 20
6234 8949 53
5168 4772 85
5044 6109 158
72 7670 132
7300 1213 837
5427 2263 1000
1785 3009 276
6136 1421 43
1629 5620 29
6445 9489 242
8443 3141 1000
4118 4307 63
1874 5238 291
1964 5785 73
7794 3934 18
3...

output:

YES
4160 6939 3841 6121
1828 4099 1566 4450
5710 4771 5901 4668
6334 1443 7300 1213
4278 321 4775 842
4160 6939 4344 6858
4718 3379 4284 3385
9940 2103 9446 2407
8040 7929 7634 8387
8914 1613 8591 1690
2381 305 2395 2085
9671 1058 8844 424
8914 1613 8844 424
63 2852 147 1148
7502 5454 6908 4386
6837...

result:

ok answer = 1

Test #7:

score: 0
Accepted
time: 3ms
memory: 12292kb

input:

300
42942 37079 222
49441 21821 1695
61023 31153 561
86630 26307 352
36940 78253 213
7841 81086 626
47425 22290 374
17694 68695 648
38259 64794 998
43599 46942 9662
9204 2816 1965
38652 83568 4057
4046 29001 1034
72591 63214 587
75984 64859 1112
70005 72177 576
34522 52126 652
56627 48785 1747
78820...

output:

YES
59944 148 59945 7276
26217 53454 15549 49146
27055 9398 30743 15955
54156 44092 54720 46175
42729 76361 46373 81005
49555 87747 48642 86091
48642 86091 49759 86207
74594 17647 77261 898
90608 87653 83657 87664
84773 93522 90608 87653
908 79893 11003 92828
62892 19999 74594 17647
44439 62520 4786...

result:

ok answer = 1

Test #8:

score: 0
Accepted
time: 3ms
memory: 12200kb

input:

1000
558504245 246224785 100000000
971981730 913036757 1821458
198791767 482624549 5998171
540520619 353988177 8924682
183178222 46223569 9859905
118485076 22129062 7497235
274928891 417171180 372954
230079763 468235825 289869
859092765 562864738 5551376
129036518 743777318 3969979
265158223 3092933...

output:

YES
969959032 159770753 935651301 194859808
407855873 545059764 387522770 540197621
709709305 895610707 803699647 926616709
957410466 524462618 951999910 625259461
805699634 244675073 842117276 266665723
21557591 472068545 9506894 429721563
703832774 417735074 606567077 439287468
944920611 405541788...

result:

ok answer = 1

Test #9:

score: 0
Accepted
time: 7ms
memory: 12380kb

input:

3000
442876143 334276354 3627270
526253918 947313397 2498956
566692880 229330019 4243066
497859604 658736917 13012787
315969653 65582717 1400013
394215653 932651144 1655676
58249045 973232518 860150
860773683 959388251 1594726
23803673 921365885 5926749
730359196 818999592 1521282
971839312 22835235...

output:

YES
290472947 49435962 281268489 57797275
338210244 314788266 336396685 305520991
504627632 484355357 511679958 472770476
385991211 898942427 381063725 888883942
109415638 638809020 106386194 648286633
443740179 557407886 445317829 548859629
278141533 211881820 287619836 198910855
43444734 915079984...

result:

ok answer = 1

Test #10:

score: 0
Accepted
time: 7ms
memory: 10296kb

input:

7000
601805179 978984160 464352
918208048 607538668 2214109
328147216 806677103 3901695
961794394 719893281 1114470
453816635 992288784 274949
778724702 692479905 1170018
169287513 886715521 576156
812072299 118324465 93778
726229729 150105801 3593039
368683874 642143790 1277375
40087476 151799345 4...

output:

YES
952741689 195407765 948962033 192473096
335978465 621454749 302136515 662205213
181702051 225543777 191910423 222317550
108639664 832228566 112166501 828136227
360578188 879715637 367657522 874112964
395639996 56994662 409421203 1671512
115667148 196841066 113675287 272880588
660724674 691603733...

result:

ok answer = 1

Test #11:

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

input:

10000
645 4710 5
1554 4072 7
6505 2760 1
6125 8212 11
9802 9537 3
6584 4356 6
1104 6649 23
4580 2623 20
3107 2460 1
4689 1662 2
7815 161 14
8718 3658 28
2900 63 15
1741 7296 44
8380 4608 50
2212 8514 4
7919 3069 17
1638 6057 3
504 9867 18
7869 8021 14
866 9239 5
3452 8042 4
9049 7222 4
4447 1004 5
9...

output:

YES
9942 7773 9941 6761
8379 5377 8980 5036
1806 9435 1140 9308
3934 629 3270 702
2042 8866 1806 9435
54 4255 588 4254
1697 6744 1698 6223
2832 3345 3511 4090
7500 3958 7950 3959
7062 3959 7500 3958
7501 4394 7500 3958
5549 7629 5924 7630
8576 4074 8575 4441
8362 3787 8576 4074
6477 9628 6424 9977
4...

result:

ok answer = 1

Test #12:

score: 0
Accepted
time: 198ms
memory: 25516kb

input:

100000
956095525 596102106 2
461544095 587257542 118
884402350 357055086 14228
547768407 186052059 263162
827807425 303694996 474924
692537425 44608243 131609
504660936 451030143 15134
207539367 899608364 20283
919236289 724317925 6
386476373 727023405 323
781914406 792770865 1064
411548762 2476126 ...

output:

YES
892145544 423239295 892696561 422861520
737182558 31629185 737205369 31606130
791386989 34057684 790259785 35554795
575900390 197298321 576712653 196103190
871840112 672618377 871778107 671901046
971859066 699788760 972388111 699494151
607697634 947278085 606473337 946634089
267828294 606295817 ...

result:

ok answer = 1

Test #13:

score: 0
Accepted
time: 397ms
memory: 34028kb

input:

200000
267774456 105702394 770
297991198 776424841 124
703700092 120262616 341808
212663821 221756923 367
195031049 705083745 66
692227605 63745620 1221
615879799 481139131 3053
93198187 239262367 141042
645539116 89213985 1679
312339485 547897747 2701
546940040 418847605 2
100457345 231142218 2
290...

output:

YES
73480409 112707894 75807544 112300029
974169585 619209298 976452843 619556934
732071653 615357564 730568325 616291877
182294625 509124843 180791485 507855412
902284179 882065660 902126642 881325390
420643702 241791571 420658973 241541045
70202096 599247436 70259530 599116568
870390405 306105841 ...

result:

ok answer = 1

Test #14:

score: 0
Accepted
time: 407ms
memory: 34948kb

input:

200000
890760596 387635202 407021
845949678 865384827 250
298937825 444813049 30
257079208 603496538 24935
825947861 514433442 276
664047255 283065064 651111
481691537 759981944 616
953630211 233077236 207
716089940 174481709 876827
807394429 737990862 50258
9195111 176890156 946
209723712 839382384...

output:

YES
701175461 366336859 700926819 363782478
258911614 139798076 259664312 140583575
571382827 413589615 572864108 412884598
59137802 682714019 59157956 682658775
890443024 926016890 892414809 926001644
632442573 782295890 631227659 780874910
917748361 850287970 917708835 849128591
392781170 94486009...

result:

ok answer = 1

Test #15:

score: 0
Accepted
time: 423ms
memory: 33760kb

input:

200000
21940906 14228149 878
947616612 637746482 278
490310177 117451293 1714712
278642428 651582650 1
214397046 727562852 3
314365021 93147008 158746
367463298 30253119 650745
816993648 678947261 4384
503557517 182822048 1116
61881753 989787068 109052
632366340 971129473 26
870552310 805607887 5436...

output:

YES
651143559 352449533 651139377 352466867
569112950 674044827 568354398 675585065
429430280 411122054 430172210 411030216
326952582 782461575 326919810 781590564
631594179 32612462 631053962 32398092
467468968 127421520 467251791 126240740
192143717 610724525 191720861 609273318
312918516 94606999...

result:

ok answer = 1

Test #16:

score: -100
Wrong Answer
time: 409ms
memory: 35176kb

input:

200000
81117 91365 1
68731 21152 3
37456 24002 2
37581 56006 3
52472 65837 1
68592 30967 2
37017 58189 11
21553 64504 95
94147 72332 80
82905 892 21
37593 40659 5
83451 10026 2
24925 11872 13
84418 48948 156
52378 43742 51
27379 10720 162
37042 54394 1
92324 20573 1
69506 96945 133
87826 40634 3
962...

output:

YES
23430 54471 23525 54295
77122 74437 76931 74403
56282 3687 56476 3688
82844 85747 82675 85836
6389 98610 6577 98611
39514 66149 39401 66000
82103 20535 82270 20536
5740 32096 5669 32227
49411 67798 49347 67669
26410 82691 26496 82804
64656 98254 64797 98255
734 69863 874 69862
9187 80898 9159 80...

result:

wrong answer Two line segments intersect, and it's not only the endpoints that intersect or line segments intersects/touches more than 2 disks