QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168619#6639. Disk Treeucup-team1209#AC ✓2743ms150032kbC++202.0kb2023-09-08 18:05:382023-09-08 18:05:39

Judging History

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

  • [2023-09-08 18:05:39]
  • 评测
  • 测评结果:AC
  • 用时:2743ms
  • 内存:150032kb
  • [2023-09-08 18:05:38]
  • 提交

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(int i = 0;i < 30;++i) {
		cp r = std::polar(1., db(gen()) / gen.max() * pi * 4);
		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: 0ms
memory: 10236kb

input:

3
1 0 3
10 10 6
0 5 1

output:

YES
1 0 0 5
10 10 0 5

result:

ok answer = 1

Test #2:

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

input:

2
1 1 1
3 3 1

output:

YES
3 3 1 1

result:

ok answer = 1

Test #3:

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

input:

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

output:

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

result:

ok answer = 1

Test #4:

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

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
98 95 99 81
45 88 48 68
29 29 17 24
17 24 0 8
28 55 48 68
45 88 17 82
17 24 34 0
17 24 28 55
45 88 98 95

result:

ok answer = 1

Test #5:

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

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

result:

ok answer = 1

Test #6:

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

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

result:

ok answer = 1

Test #7:

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

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
59945 7276 59944 148
26217 53454 15549 49146
30743 15955 27055 9398
54156 44092 54720 46175
46373 81005 42729 76361
48642 86091 49555 87747
49759 86207 48642 86091
77261 898 74594 17647
90608 87653 83657 87664
9726 31739 710 39900
84773 93522 90608 87653
11003 92828 908 79893
62892 19999 74594 1...

result:

ok answer = 1

Test #8:

score: 0
Accepted
time: 9ms
memory: 12436kb

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
792974301 599903526 758581132 629433365
803699647 926616709 709709305 895610707
951999910 625259461 957410466 524462618
805699634 244675073 842117276 266665723
21557591 472068545 9506894 429721563
606567077 439287468...

result:

ok answer = 1

Test #9:

score: 0
Accepted
time: 22ms
memory: 13724kb

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
336396685 305520991 338210244 314788266
504627632 484355357 511679958 472770476
381063725 888883942 385991211 898942427
106386194 648286633 109415638 638809020
443740179 557407886 445317829 548859629
278141533 211881820 287619836 198910855
34366085 912644950...

result:

ok answer = 1

Test #10:

score: 0
Accepted
time: 62ms
memory: 17464kb

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
948962033 192473096 952741689 195407765
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: 90ms
memory: 20216kb

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
7950 3959 7500 3958
7062 3959 7500 3958
7501 4394 7500 3958
5549 7629 5924 7630
8575 4441 8576 4074
8362 3787 8576 4074
6424 9977 6477 9628
4...

result:

ok answer = 1

Test #12:

score: 0
Accepted
time: 1191ms
memory: 81596kb

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
892696561 422861520 892145544 423239295
737205369 31606130 737182558 31629185
790259785 35554795 791386989 34057684
576712653 196103190 575900390 197298321
871778107 671901046 871840112 672618377
972388111 699494151 971859066 699788760
606473337 946634089 607697634 947278085
268325283 605404505 ...

result:

ok answer = 1

Test #13:

score: 0
Accepted
time: 2743ms
memory: 149400kb

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
976452843 619556934 974169585 619209298
730568325 616291877 732071653 615357564
182294625 509124843 180791485 507855412
902126642 881325390 902284179 882065660
420643702 241791571 420658973 241541045
70202096 599247436 70259530 599116568
870320516 304339112 ...

result:

ok answer = 1

Test #14:

score: 0
Accepted
time: 2614ms
memory: 149388kb

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
700926819 363782478 701175461 366336859
259664312 140583575 258911614 139798076
572864108 412884598 571382827 413589615
59137802 682714019 59157956 682658775
890443024 926016890 892414809 926001644
632442573 782295890 631227659 780874910
917708835 849128591 917748361 850287970
393578748 94352366...

result:

ok answer = 1

Test #15:

score: 0
Accepted
time: 2547ms
memory: 148628kb

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
430172210 411030216 429430280 411122054
326919810 781590564 326952582 782461575
631594179 32612462 631053962 32398092
467251791 126240740 467468968 127421520
192143717 610724525 191720861 609273318
312918516 94606999...

result:

ok answer = 1

Test #16:

score: 0
Accepted
time: 2636ms
memory: 148852kb

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
23525 54295 23430 54471
56282 3687 56476 3688
76931 74403 77122 74437
82844 85747 82675 85836
6389 98610 6577 98611
39401 66000 39514 66149
82270 20536 82103 20535
5669 32227 5740 32096
49411 67798 49347 67669
26410 82691 26496 82804
64656 98254 64797 98255
734 69863 874 69862
22895 40921 22815 ...

result:

ok answer = 1

Test #17:

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

input:

10000
126758371 588314899 812231
238086622 378023315 890058
477126060 14900711 1191393
511712433 35095827 204725
651796639 43378716 2018310
308442866 596282834 2328087
42294570 231322805 1602825
168464157 357054887 2277954
224671652 693289331 2062259
616695889 175688410 1253251
385431057 29127383 18...

output:

YES
560958114 617164119 560494445 623074186
217879509 43380606 217827870 49054754
455147661 483312868 449291442 483938555
595298590 693094619 589328535 693506727
567256064 399531498 561301690 400090826
232368285 266114482 232326691 260271185
351317762 42119768 357064448 42290912
315904849 98254739 3...

result:

ok answer = 1

Test #18:

score: 0
Accepted
time: 410ms
memory: 48728kb

input:

40000
290669648 662085507 804601
669033554 119055358 638805
105668336 570987547 641107
70398923 679676225 1151529
67163601 217283316 655911
266292842 490670500 288695
332954119 213678087 316383
133514562 301390490 1150957
189198028 430695918 498385
52533444 508154472 662055
675557474 175423882 71076...

output:

YES
630142151 514500404 630170052 511619062
679211500 308695311 679535718 311526254
389136492 18154644 392052205 18003654
245332148 409612345 245478707 406693327
651602297 66919393 654527956 67086937
290629392 273688668 291105690 276509416
63480942 175676698 63314166 178503394
613190379 455640998 61...

result:

ok answer = 1

Test #19:

score: 0
Accepted
time: 906ms
memory: 81796kb

input:

79806
675311888 175949323 45152
668303725 415877398 705454
526993355 106652475 101518
306843353 465414670 733685
235164634 54490010 250702
237718215 128806833 416572
47406184 660535125 231461
217980403 334240174 311035
438155656 608919183 741482
175786440 138973185 691587
383453409 420621369 23780
1...

output:

YES
230073400 190485654 230134586 188450377
146249195 30169566 146065096 32173130
331912211 133939178 333929066 133580336
161269230 86938192 163297178 86766467
146401730 108908862 148415088 109129130
195424253 628642356 193367222 628566097
267138014 477739352 265157855 477556415
277075386 591261162 ...

result:

ok answer = 1

Test #20:

score: 0
Accepted
time: 2684ms
memory: 150032kb

input:

199809
330527920 105087498 120223
601378677 222559216 191284
604605920 449476822 241005
435487497 286817733 303877
682929431 10980946 280834
393289259 673421713 256371
217818174 324382996 403684
307178253 324362921 334561
321290021 314861063 288503
661144513 394874427 31218
664021225 319719526 14923...

output:

YES
391763233 19099771 391621055 20363768
277455310 228822213 278751941 228774360
490433726 571671782 491738636 571704586
134699333 87705756 134742299 86440904
333804906 170698191 333558515 169436030
631123797 258610720 629830991 258615725
53271247 430845238 51980457 430859195
667119868 127066375 66...

result:

ok answer = 1

Test #21:

score: 0
Accepted
time: 1126ms
memory: 148112kb

input:

200000
500000000 500000000 450000000
950000002 500000000 1
950000002 500014137 1
950000001 500028274 1
950000000 500042412 1
949999998 500056549 1
949999996 500070686 1
949999994 500084823 1
949999991 500098961 1
949999988 500113098 1
949999984 500127235 1
949999980 500141372 1
949999975 500155510 1...

output:

YES
820100409 183715746 500000000 500000000
820100409 816284254 500000000 500000000
195908774 831705483 500000000 500000000
195908774 168294517 500000000 500000000
779001277 853069807 500000000 500000000
779001277 146930193 500000000 500000000
819394128 183002536 500000000 500000000
819394128 816997...

result:

ok answer = 1

Test #22:

score: 0
Accepted
time: 494ms
memory: 83316kb

input:

200000
1666 1666 1666
6664 1666 1666
11662 1666 1666
16660 1666 1666
21658 1666 1666
26656 1666 1666
31654 1666 1666
36652 1666 1666
41650 1666 1666
46648 1666 1666
51646 1666 1666
56644 1666 1666
61642 1666 1666
66640 1666 1666
71638 1666 1666
76636 1666 1666
81634 1666 1666
86632 1666 1666
91630 1...

output:

YES
333173344 1666 333178342 1666
333233320 1666 333238318 1666
333228322 1666 333233320 1666
333223324 1666 333228322 1666
333218326 1666 333223324 1666
333213328 1666 333218326 1666
333208330 1666 333213328 1666
333203332 1666 333208330 1666
333198334 1666 333203332 1666
333193336 1666 333198334 1...

result:

ok answer = 1

Test #23:

score: 0
Accepted
time: 727ms
memory: 83244kb

input:

200000
1276 2177 1666
6143 1271 1666
12177 1577 1666
17105 1415 1666
21414 1758 1666
27078 1291 1666
31751 1856 1666
36681 2166 1666
42165 1914 1666
46298 2207 1666
51434 1925 1666
56782 1717 1666
61708 1408 1666
66612 1280 1666
71599 2168 1666
76405 1971 1666
81489 1694 1666
86696 2187 1666
91352 1...

output:

YES
811211499 1462 811207609 1471
657384161 1609 657388057 1495
39790200 2034 39786301 2129
383457674 1302 383453777 1498
49991113 1431 49987213 1288
392004261 1179 392000357 1160
861607428 1921 861611331 1793
807134239 1791 807138129 2135
149132529 1870 149136434 1981
864395218 1216 864391311 1204
...

result:

ok answer = 1

Test #24:

score: 0
Accepted
time: 490ms
memory: 84604kb

input:

200000
1666 1666 1666
6588 2534 1666
11510 3402 1666
16432 4270 1666
21354 5138 1666
26276 6005 1666
31198 6873 1666
36120 7741 1666
41043 8609 1666
45965 9477 1666
50887 10345 1666
55809 11213 1666
60731 12081 1666
65653 12949 1666
70575 13817 1666
75497 14684 1666
80419 15552 1666
85341 16420 1666...

output:

YES
705388318 124380365 705393240 124381232
705201279 124347385 705206201 124348252
287420972 50681444 287416050 50680577
777368657 137072440 777363735 137071573
705250500 124356064 705255422 124356931
777412956 137080251 777408034 137079384
88559534 15616808 88564456 15617675
705294799 124363875 70...

result:

ok answer = 1

Test #25:

score: 0
Accepted
time: 492ms
memory: 84028kb

input:

200000
1666 1666 1666
1666 6664 1666
1666 11662 1666
1666 16660 1666
1666 21658 1666
1666 26656 1666
1666 31654 1666
1666 36652 1666
1666 41650 1666
1666 46648 1666
1666 51646 1666
1666 56644 1666
1666 61642 1666
1666 66640 1666
1666 71638 1666
1666 76636 1666
1666 81634 1666
1666 86632 1666
1666 91...

output:

YES
1666 26656 1666 21658
1666 31654 1666 36652
1666 26656 1666 31654
1666 16660 1666 21658
1666 11662 1666 16660
1666 6664 1666 11662
1666 1666 1666 6664
1666 36652 1666 41650
1666 46648 1666 41650
1666 51646 1666 46648
1666 56644 1666 51646
1666 61642 1666 56644
1666 66640 1666 61642
1666 71638 16...

result:

ok answer = 1

Test #26:

score: 0
Accepted
time: 700ms
memory: 83132kb

input:

200000
1238 1279 1666
1911 6266 1666
1278 11483 1666
1657 16880 1666
1637 22064 1666
1629 26455 1666
2087 31415 1666
1150 36477 1666
2020 41228 1666
1277 46249 1666
1331 51188 1666
1274 56871 1666
1709 61810 1666
1509 66281 1666
1922 71932 1666
2188 76257 1666
1947 81675 1666
2124 86511 1666
1231 91...

output:

YES
1441 805498786 1481 805494895
1575 786467509 1360 786471398
1631 728499598 1654 728495702
1167 772991800 1194 772987900
1148 7204330 1266 7208229
2081 807687910 1942 807684010
1245 639661242 1308 639665146
2158 712896935 2203 712900840
1507 924806045 1653 924802141
1768 893244779 1390 893248670
...

result:

ok answer = 1

Test #27:

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

input:

2
1000000000 1000000000 1000000000
0 0 1

output:

YES
0 0 1000000000 1000000000

result:

ok answer = 1

Test #28:

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

input:

2
1000000000 1000000000 500000000
0 1000000000 499999999

output:

YES
1000000000 1000000000 0 1000000000

result:

ok answer = 1

Test #29:

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

input:

2
0 1000000000 499999999
0 0 500000000

output:

YES
0 1000000000 0 0

result:

ok answer = 1

Test #30:

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

input:

2
1000000000 1000000000 499999999
1000000000 0 500000000

output:

YES
1000000000 0 1000000000 1000000000

result:

ok answer = 1