QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671016#218. 二维凸包yhdddAC ✓31ms8612kbC++201.6kb2024-10-24 09:54:062024-10-24 09:54:07

Judging History

This is the latest submission verdict.

  • [2024-10-24 09:54:07]
  • Judged
  • Verdict: AC
  • Time: 31ms
  • Memory: 8612kb
  • [2024-10-24 09:54:06]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int maxn=200010;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n;
pii a[maxn];
int st[maxn],tp;
void work(){
	n=read();
	for(int i=1;i<=n;i++)a[i]={read(),read()};
	sort(a+1,a+n+1);st[++tp]=1;
	for(int i=2;i<=n;i++){
		while(tp>1&&(a[st[tp]].se-a[st[tp-1]].se)*(a[i].fi-a[st[tp-1]].fi)<=(a[i].se-a[st[tp-1]].se)*(a[st[tp]].fi-a[st[tp-1]].fi))tp--;
		st[++tp]=i;
	}
	db ans=0;
	for(int i=2;i<=tp;i++)ans+=sqrt(1.0*(a[st[i]].fi-a[st[i-1]].fi)*(a[st[i]].fi-a[st[i-1]].fi)+(a[st[i]].se-a[st[i-1]].se)*(a[st[i]].se-a[st[i-1]].se));
	tp=0;
	st[++tp]=1;
	for(int i=2;i<=n;i++){
		while(tp>1&&(a[st[tp]].se-a[st[tp-1]].se)*(a[i].fi-a[st[tp-1]].fi)>=(a[i].se-a[st[tp-1]].se)*(a[st[tp]].fi-a[st[tp-1]].fi))tp--;
		st[++tp]=i;
	}
	for(int i=2;i<=tp;i++)ans+=sqrt(1.0*(a[st[i]].fi-a[st[i-1]].fi)*(a[st[i]].fi-a[st[i-1]].fi)+(a[st[i]].se-a[st[i-1]].se)*(a[st[i]].se-a[st[i-1]].se));
	printf("%.16lf\n",ans);
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=1;
	while(T--)work();
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

5
1 2
1 4
2 3
3 5
4 2

output:

10.3983456376681698

result:

ok found '10.3983456', expected '10.3983456', error '0.0000000'

Test #2:

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

input:

9
1 3
1 7
2 2
2 5
2 9
3 4
3 6
4 1
5 5

output:

19.0094551429903369

result:

ok found '19.0094551', expected '19.0094551', error '0.0000000'

Test #3:

score: 0
Accepted
time: 12ms
memory: 6564kb

input:

128312
5578014 410408218
5585076 410404717
5588011 410403262
5588473 410403033
5589740 410402405
5593295 410400643
5593751 410400417
5597248 410398684
5598935 410397848
5600618 410397014
5605185 410394751
5610514 410392111
5614281 410390245
5617263 410388768
5621142 410386847
5630840 410382045
56310...

output:

628318532.0324112176895142

result:

ok found '628318532.0324112', expected '628318532.0324112', error '0.0000000'

Test #4:

score: 0
Accepted
time: 13ms
memory: 8132kb

input:

128086
149550602 509469827
149551059 509465022
149551336 509462107
149551964 509455497
149552572 509449094
149553350 509440895
149553656 509437667
149554161 509432339
149554254 509431357
149554545 509428284
149555017 509423299
149555366 509419611
149555842 509414580
149556382 509408867
149556564 509...

output:

628318532.0320754051208496

result:

ok found '628318532.0320754', expected '628318532.0320754', error '0.0000000'

Test #5:

score: 0
Accepted
time: 16ms
memory: 8324kb

input:

128369
146452483 526399214
146453715 526394712
146454820 526390674
146456370 526385008
146457099 526382343
146457964 526379180
146458751 526376302
146460091 526371401
146460722 526369093
146461114 526367659
146462323 526363236
146463053 526360565
146464791 526354204
146465863 526350280
146467488 526...

output:

628318532.0296231508255005

result:

ok found '628318532.0296232', expected '628318532.0296232', error '0.0000000'

Test #6:

score: 0
Accepted
time: 17ms
memory: 6468kb

input:

128629
-49533670 490353833
-49532992 490346840
-49532611 490342912
-49531898 490335566
-49531313 490329543
-49531185 490328226
-49530713 490323370
-49530074 490316799
-49529672 490312668
-49528947 490305222
-49528647 490302143
-49528203 490297587
-49527568 490291076
-49527548 490290871
-49527039 490...

output:

628318532.0306160449981689

result:

ok found '628318532.0306160', expected '628318532.0306160', error '0.0000000'

Test #7:

score: 0
Accepted
time: 17ms
memory: 8084kb

input:

128259
75790065 403382855
75793744 403383837
75801054 403385789
75805360 403386939
75810275 403388252
75813681 403389162
75820264 403390921
75830809 403393740
75832118 403394090
75837226 403395456
75840000 403396198
75844837 403397492
75849584 403398762
75852835 403399632
75860658 403401726
75865562...

output:

628318532.0301942825317383

result:

ok found '628318532.0301943', expected '628318532.0301943', error '0.0000000'

Test #8:

score: 0
Accepted
time: 14ms
memory: 7336kb

input:

128166
46176199 599926866
46170746 599926657
46165737 599926465
46159641 599926231
46152002 599925937
46147638 599925769
46143595 599925613
46138544 599925418
46131124 599925131
46125834 599924926
46120627 599924724
46118799 599924653
46115505 599924525
46110055 599924313
46109413 599924288
46107744...

output:

628318532.0342986583709717

result:

ok found '628318532.0342987', expected '628318532.0342987', error '0.0000000'

Test #9:

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

input:

128507
149999857 500169091
149999867 500163069
149999868 500162459
149999880 500154866
149999887 500150300
149999898 500142815
149999902 500139971
149999913 500131887
149999918 500128019
149999923 500124046
149999926 500121605
149999929 500119099
149999933 500115702
149999941 500108613
149999946 500...

output:

628318532.0310424566268921

result:

ok found '628318532.0310425', expected '628318532.0310425', error '0.0000000'

Test #10:

score: 0
Accepted
time: 16ms
memory: 6540kb

input:

128133
140873382 458262385
140873715 458263110
140876530 458269240
140878601 458273750
140879764 458276283
140880913 458278786
140884549 458286707
140886668 458291324
140890730 458300177
140893254 458305679
140895530 458310641
140897744 458315468
140900237 458320905
140902076 458324916
140904176 458...

output:

628318532.0290125608444214

result:

ok found '628318532.0290126', expected '628318532.0290126', error '0.0000000'

Test #11:

score: 0
Accepted
time: 16ms
memory: 8200kb

input:

128319
18407912 594878554
18403065 594876940
18399018 594875592
18391672 594873145
18389499 594872421
18386714 594871493
18383857 594870541
18370816 594866194
18363997 594863920
18356279 594861346
18349086 594858946
18343059 594856935
18338283 594855341
18334712 594854149
18329890 594852539
18326410...

output:

628318532.0314702987670898

result:

ok found '628318532.0314703', expected '628318532.0314703', error '0.0000000'

Test #12:

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

input:

128502
10448094 591845777
10450502 591846814
10453758 591848216
10459200 591850559
10461337 591851479
10463544 591852429
10473696 591856798
10479318 591859217
10480608 591859772
10483502 591861017
10487533 591862751
10490644 591864089
10494176 591865608
10495627 591866232
10505163 591870332
10509490...

output:

628318532.0324751138687134

result:

ok found '628318532.0324751', expected '628318532.0324751', error '0.0000000'

Test #13:

score: 0
Accepted
time: 31ms
memory: 8612kb

input:

200000
735694576 818938578
987827151 938346376
8872493 740881229
978011120 920925524
751086177 527244376
941593052 866230823
621373018 698294913
942445996 904283273
994218901 555705628
973060874 945700279
982497944 445604243
363374742 200218343
33318887 294315485
360381102 750060766
908267893 188473...

output:

3986080664.9024820327758789

result:

ok found '3986080664.9024820', expected '3986080664.9024820', error '0.0000000'

Test #14:

score: 0
Accepted
time: 31ms
memory: 7872kb

input:

200000
141614041 20129991
852494790 990438031
414525795 381987987
849813906 483555176
625761555 56539650
211089643 991635060
478768964 324954055
520252140 235494160
289660392 775908634
356320764 190183252
222649234 14752168
237857187 534729801
472792168 657148553
304006221 412837022
493539695 731188...

output:

3990743029.1043782234191895

result:

ok found '3990743029.1043782', expected '3990743029.1043782', error '0.0000000'

Test #15:

score: 0
Accepted
time: 27ms
memory: 7320kb

input:

200000
687815604 664051585
102936607 682777022
603082129 674642969
182042008 837402820
390581774 25695807
802427416 834782205
447005641 539018559
594272992 929361370
316763967 596615977
388230238 433334015
281726723 371063288
948749564 292061003
513434498 596386289
313666835 863186260
302007334 8037...

output:

3988549000.4701919555664062

result:

ok found '3988549000.4701920', expected '3988549000.4701920', error '0.0000000'

Test #16:

score: 0
Accepted
time: 27ms
memory: 8132kb

input:

200000
500840708 783778982
154673584 381799518
220956457 685191601
768046912 176521830
761465371 176456122
833461155 552597357
351159065 388832000
818908577 464398998
282415771 531567737
37979476 51086758
173604097 815819079
183374861 831477469
317966904 341500960
487655714 604963276
937137788 27529...

output:

3995737796.9796433448791504

result:

ok found '3995737796.9796433', expected '3995737796.9796433', error '0.0000000'

Test #17:

score: 0
Accepted
time: 31ms
memory: 7584kb

input:

200000
690184671 293843101
790008236 257459263
222357368 320442807
905478811 181140745
26326095 722645862
663711295 320830105
76810753 792189420
516514407 988624450
848950838 775986552
146182431 270044578
525579480 431651853
482244227 900953394
396206365 303466945
457538303 219731463
394616828 67234...

output:

3990226458.8802947998046875

result:

ok found '3990226458.8802948', expected '3990226458.8802948', error '0.0000000'

Test #18:

score: 0
Accepted
time: 27ms
memory: 6916kb

input:

200000
657854975 611131241
300028692 935854458
940121389 582890745
146218889 308553639
847425325 23616588
881979776 987442973
749420223 770082716
985518195 947466999
428638864 673313606
735933731 91096870
695706449 648215949
962088966 141474880
369147722 86138733
816165 219713134
573244229 390397851...

output:

3990633199.3662996292114258

result:

ok found '3990633199.3662996', expected '3990633199.3662996', error '0.0000000'

Test #19:

score: 0
Accepted
time: 31ms
memory: 8016kb

input:

200000
249020267 550126468
739760535 860390801
177737841 96227007
415939003 407302136
896931132 669276127
336553079 828740157
292543362 700321202
877598583 336772992
505726614 216080629
795137263 12267460
733949312 955149139
262557379 955615975
681637174 583910525
193048753 124158444
842464782 85615...

output:

3990303414.0937447547912598

result:

ok found '3990303414.0937448', expected '3990303414.0937448', error '0.0000000'

Test #20:

score: 0
Accepted
time: 23ms
memory: 7380kb

input:

200000
605159104 560953964
796889988 702651482
127707930 733152630
204488972 581897368
957306436 753221497
760144168 881943745
176367161 685270652
40867502 13971562
6840418 867403486
753804894 729749002
297747820 309648279
844758236 785591924
120168025 360714741
52612615 76453825
367971434 667417728...

output:

3991117137.0151572227478027

result:

ok found '3991117137.0151572', expected '3991117137.0151572', error '0.0000000'

Test #21:

score: 0
Accepted
time: 31ms
memory: 8584kb

input:

200000
708900575 19848686
85053643 11843429
719771627 197337073
301027308 130095501
33933509 301588319
102931272 657076078
183875247 508919739
176865264 232910
62131411 137500551
228321872 189958481
834040311 588493210
7219545 567280587
442509609 909564186
528175892 525394616
294136146 950388221
908...

output:

3989225203.5250177383422852

result:

ok found '3989225203.5250177', expected '3989225203.5250177', error '0.0000000'

Test #22:

score: 0
Accepted
time: 26ms
memory: 8564kb

input:

200000
321635921 951848473
665877255 695961241
803722830 226287089
215972728 12133623
487624619 349446506
892735444 323463255
709247371 23257513
598539740 313863748
713197569 234415446
840120662 313786330
410772703 936435584
100665598 410792800
819136236 974508326
127451189 73845287
710626942 442797...

output:

3989869884.5733766555786133

result:

ok found '3989869884.5733767', expected '3989869884.5733767', error '0.0000000'

Test #23:

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

input:

100
830921 230613
268715 242158
371070 202780
614375 4522
164598 792621
328763 908910
311284 638954
867447 319900
203890 750795
583668 440572
865698 683924
266973 496167
763754 895210
963791 460716
93578 562915
782688 159186
988337 908521
211850 551430
659532 281873
327291 205111
609907 433491
88487...

output:

3672552.4999379119835794

result:

ok found '3672552.4999379', expected '3672552.4999379', error '0.0000000'

Test #24:

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

input:

800
661283 389669
127389 813994
365651 92995
453965 237629
505342 483107
838283 615362
156875 38232
675453 150209
491394 707068
248621 933290
415854 871642
4834 702389
326235 543058
817854 87493
196234 341894
501593 130866
780604 895548
323901 765471
499724 271522
736360 545936
738412 624262
873664 ...

output:

3858694.6336230882443488

result:

ok found '3858694.6336231', expected '3858694.6336231', error '0.0000000'

Test #25:

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

input:

2700
226841 963786
349701 142082
730573 190855
573914 26114
246344 223247
17665 987975
968605 440807
875139 697665
52990 621022
767766 435846
698397 759481
893921 404793
65243 550317
743381 977050
870168 8624
227056 298729
73859 206263
316148 960704
489578 429067
211887 49547
545423 69855
861352 593...

output:

3942037.4407599349506199

result:

ok found '3942037.4407599', expected '3942037.4407599', error '0.0000000'

Test #26:

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

input:

6400
752667 923942
96391 981638
196815 55704
498562 101097
756587 565215
950204 286225
161109 716554
771642 302074
367202 762722
660501 490197
980757 619857
119985 953074
457862 601650
22960 305995
222548 53983
851274 687824
493266 986891
630042 435521
977317 121300
767453 730654
216187 483997
56804...

output:

3960673.8688767445273697

result:

ok found '3960673.8688767', expected '3960673.8688767', error '0.0000000'

Test #27:

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

input:

12500
398309 148239
481109 132059
679932 41908
985253 6057
255836 741175
161155 990495
52046 219562
285859 865577
836685 271291
285182 142208
859617 215939
279642 74333
779768 77263
997146 318848
936952 977670
474435 294077
825645 105136
535286 72081
477660 120308
425944 330150
278034 32490
106658 2...

output:

3966939.8951655947603285

result:

ok found '3966939.8951656', expected '3966939.8951656', error '0.0000000'

Test #28:

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

input:

21600
809654 923856
510104 580379
181089 551442
461285 550359
577512 176693
173264 506457
74234 988681
162023 918068
117878 783518
857409 388038
802628 409324
70787 107455
928723 35275
306685 919990
558018 104743
724448 197038
507283 396812
801208 473850
502628 806278
800887 222869
451059 554368
819...

output:

3964869.9358011153526604

result:

ok found '3964869.9358011', expected '3964869.9358011', error '0.0000000'

Test #29:

score: 0
Accepted
time: 5ms
memory: 5868kb

input:

34300
253765 174712
981822 30547
528469 857005
158667 347386
213751 122939
919347 944995
203601 584833
35248 841054
177669 310458
199642 361914
859208 746759
857104 362519
273779 187634
880660 835896
908028 566640
932893 64119
832902 276624
837068 824366
463171 289020
374299 822369
35820 960883
7945...

output:

3969745.5213701878674328

result:

ok found '3969745.5213702', expected '3969745.5213702', error '0.0000000'

Test #30:

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

input:

51200
336255 187310
227806 191556
240364 445693
293383 902027
252481 220936
655506 61617
467904 821929
278044 85219
256110 57420
100340 465944
556239 458558
955339 579336
993736 433183
782675 666134
591875 425382
907760 750633
697434 318634
441318 699417
627409 995844
692089 689091
738518 382454
251...

output:

3978880.1726750666275620

result:

ok found '3978880.1726751', expected '3978880.1726751', error '0.0000000'

Test #31:

score: 0
Accepted
time: 5ms
memory: 7896kb

input:

72900
295661 486006
406714 103823
944202 247984
51489 824557
313364 378890
656895 589193
765276 41682
310035 823335
420943 996929
749587 101511
394788 465595
108226 721781
391630 83879
347487 79196
660332 462183
549249 824468
733386 980495
669398 2340
801160 461440
625440 279082
512455 429105
83851 ...

output:

3982178.8025236930698156

result:

ok found '3982178.8025237', expected '3982178.8025237', error '0.0000000'

Test #32:

score: 0
Accepted
time: 14ms
memory: 5920kb

input:

100000
986823 682888
228182 573409
896040 458122
31976 802147
411056 477305
767442 228948
236996 245123
198615 160169
368203 738579
546438 241989
678440 883552
479373 917944
128484 214595
574052 877378
909893 940331
796322 462418
803364 636226
891596 105759
992641 939896
163706 18668
788387 384424
2...

output:

3982215.6858737096190453

result:

ok found '3982215.6858737', expected '3982215.6858737', error '0.0000000'

Test #33:

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

input:

3
0 0
1 0
0 1

output:

3.4142135623730949

result:

ok found '3.4142136', expected '3.4142136', error '0.0000000'

Test #34:

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

input:

4
0 0
0 1
1 1
1 0

output:

4.0000000000000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #35:

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

input:

4
0 0
0 3
1 2
1 1

output:

6.8284271247461898

result:

ok found '6.8284271', expected '6.8284271', error '0.0000000'

Test #36:

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

input:

5
1 0
4 1
0 1
2 0
3 2

output:

9.2267727624143596

result:

ok found '9.2267728', expected '9.2267728', error '0.0000000'

Test #37:

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

input:

5
0 0
1000000000 0
1000000000 500000000
1000000000 1000000000
0 1000000000

output:

4000000000.0000000000000000

result:

ok found '4000000000.0000000', expected '4000000000.0000000', error '0.0000000'

Test #38:

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

input:

5
0 0
1000000000 0
1000000000 499999999
1000000000 1000000000
0 1000000000

output:

4000000000.0000000000000000

result:

ok found '4000000000.0000000', expected '4000000000.0000000', error '0.0000000'

Test #39:

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

input:

5
0 0
999999999 0
1000000000 50000000
999999999 1000000000
0 1000000000

output:

3999999998.0000000000000000

result:

ok found '3999999998.0000000', expected '3999999998.0000000', error '0.0000000'

Test #40:

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

input:

3
0 0
0 0
0 0

output:

0.0000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #41:

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

input:

8
0 0
2 2
3 1
2 0
1 1
2 2
4 0
2 -2

output:

11.3137084989847612

result:

ok found '11.3137085', expected '11.3137085', error '0.0000000'

Test #42:

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

input:

8
0 0
1 0
1 1
0 1
-1 -1
2 -1
2 2
-1 2

output:

12.0000000000000000

result:

ok found '12.0000000', expected '12.0000000', error '0.0000000'

Test #43:

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

input:

3
0 0
1000000000 1000000000
-1000000000 -999999999

output:

5656854248.0781669616699219

result:

ok found '5656854248.0781670', expected '5656854248.0781670', error '0.0000000'

Test #44:

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

input:

63106
142555391 -989786825
142628513 -989776291
142733479 -989761159
142876092 -989740583
143089114 -989709808
143192330 -989694880
143443376 -989658525
143457992 -989656407
143512227 -989648543
143552582 -989642691
143828488 -989602630
143882018 -989594848
143928651 -989588067
144020124 -989574759
...

output:

6283185291.4582920074462891

result:

ok found '6283185291.4582920', expected '6283185291.4583521', error '0.0000000'

Test #45:

score: 0
Accepted
time: 14ms
memory: 8164kb

input:

95217
-920449752 390860912
-920451998 390855623
-920493764 390757252
-920558815 390603977
-920565821 390587465
-920604170 390497070
-920612754 390476832
-920645198 390400331
-920653034 390381852
-920668869 390344506
-920675430 390329030
-920715025 390235623
-920738255 390180809
-920751302 390150021
...

output:

6283185299.4922342300415039

result:

ok found '6283185299.4922342', expected '6283185299.4922733', error '0.0000000'