QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#473561 | #218. 二维凸包 | Wuyanru# | AC ✓ | 28ms | 6948kb | C++14 | 1.3kb | 2024-07-12 10:02:50 | 2024-07-12 10:02:51 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
struct node
{
int x,y;
}a[200001];
int sta[200001],top;
int vis[200001];
ld ans;
int n;
inline bool check(int p1,int p2,int p3)
{
ll A=a[p2].x-a[p1].x,B=a[p2].y-a[p1].y;
ll C=a[p3].x-a[p2].x,D=a[p3].y-a[p2].y;
return A*D-B*C<0;
}
inline ld get(int p1,int p2)
{
ll x=a[p1].x-a[p2].x,y=a[p1].y-a[p2].y;
return sqrtl(x*x+y*y);
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
sort(a+1,a+n+1,[](node a,node b){ return a.x<b.x;});
top=0;
for(int i=1;i<=n;i++)
{
while(top>=2&&!check(sta[top-1],sta[top],i)) top--;
sta[++top]=i;
}
for(int i=2;i<=top;i++) ans+=get(sta[i-1],sta[i]);
top=0;
for(int i=n;i;i--)
{
while(top>=2&&!check(sta[top-1],sta[top],i)) top--;
sta[++top]=i;
}
for(int i=2;i<=top;i++) ans+=get(sta[i-1],sta[i]);
printf("%.8Lf\n",ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
input:
5 1 2 1 4 2 3 3 5 4 2
output:
10.39834564
result:
ok found '10.3983456', expected '10.3983456', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5900kb
input:
9 1 3 1 7 2 2 2 5 2 9 3 4 3 6 4 1 5 5
output:
19.00945514
result:
ok found '19.0094551', expected '19.0094551', error '0.0000000'
Test #3:
score: 0
Accepted
time: 16ms
memory: 5148kb
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.03240781
result:
ok found '628318532.0324078', expected '628318532.0324112', error '0.0000000'
Test #4:
score: 0
Accepted
time: 15ms
memory: 5924kb
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.03207340
result:
ok found '628318532.0320734', expected '628318532.0320754', error '0.0000000'
Test #5:
score: 0
Accepted
time: 15ms
memory: 5120kb
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.02962765
result:
ok found '628318532.0296277', expected '628318532.0296232', error '0.0000000'
Test #6:
score: 0
Accepted
time: 16ms
memory: 5120kb
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.03061455
result:
ok found '628318532.0306145', expected '628318532.0306160', error '0.0000000'
Test #7:
score: 0
Accepted
time: 16ms
memory: 6048kb
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.03018096
result:
ok found '628318532.0301809', expected '628318532.0301943', error '0.0000000'
Test #8:
score: 0
Accepted
time: 16ms
memory: 5116kb
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.03430748
result:
ok found '628318532.0343075', expected '628318532.0342987', error '0.0000000'
Test #9:
score: 0
Accepted
time: 16ms
memory: 4960kb
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.03104624
result:
ok found '628318532.0310463', expected '628318532.0310425', error '0.0000000'
Test #10:
score: 0
Accepted
time: 15ms
memory: 6180kb
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.02900917
result:
ok found '628318532.0290092', expected '628318532.0290126', error '0.0000000'
Test #11:
score: 0
Accepted
time: 15ms
memory: 5924kb
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.03146957
result:
ok found '628318532.0314696', expected '628318532.0314703', error '0.0000000'
Test #12:
score: 0
Accepted
time: 16ms
memory: 5992kb
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.03247641
result:
ok found '628318532.0324764', expected '628318532.0324751', error '0.0000000'
Test #13:
score: 0
Accepted
time: 24ms
memory: 5296kb
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.90248199
result:
ok found '3986080664.9024820', expected '3986080664.9024820', error '0.0000000'
Test #14:
score: 0
Accepted
time: 28ms
memory: 6032kb
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.10437697
result:
ok found '3990743029.1043768', expected '3990743029.1043782', error '0.0000000'
Test #15:
score: 0
Accepted
time: 28ms
memory: 5448kb
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.47019162
result:
ok found '3988549000.4701915', expected '3988549000.4701920', error '0.0000000'
Test #16:
score: 0
Accepted
time: 21ms
memory: 6456kb
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.97964422
result:
ok found '3995737796.9796443', expected '3995737796.9796433', error '0.0000000'
Test #17:
score: 0
Accepted
time: 28ms
memory: 6948kb
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.88029504
result:
ok found '3990226458.8802953', expected '3990226458.8802948', error '0.0000000'
Test #18:
score: 0
Accepted
time: 28ms
memory: 6628kb
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.36630007
result:
ok found '3990633199.3663001', expected '3990633199.3662996', error '0.0000000'
Test #19:
score: 0
Accepted
time: 24ms
memory: 6660kb
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.09374626
result:
ok found '3990303414.0937462', expected '3990303414.0937448', error '0.0000000'
Test #20:
score: 0
Accepted
time: 28ms
memory: 6808kb
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.01515760
result:
ok found '3991117137.0151577', expected '3991117137.0151572', error '0.0000000'
Test #21:
score: 0
Accepted
time: 28ms
memory: 6764kb
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.52501774
result:
ok found '3989225203.5250177', expected '3989225203.5250177', error '0.0000000'
Test #22:
score: 0
Accepted
time: 28ms
memory: 6356kb
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.57337662
result:
ok found '3989869884.5733767', expected '3989869884.5733767', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3860kb
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.49993791
result:
ok found '3672552.4999379', expected '3672552.4999379', error '0.0000000'
Test #24:
score: 0
Accepted
time: 1ms
memory: 5784kb
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.63362309
result:
ok found '3858694.6336231', expected '3858694.6336231', error '0.0000000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 5912kb
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.44075994
result:
ok found '3942037.4407599', expected '3942037.4407599', error '0.0000000'
Test #26:
score: 0
Accepted
time: 1ms
memory: 5928kb
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.86887674
result:
ok found '3960673.8688767', expected '3960673.8688767', error '0.0000000'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3980kb
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.89516559
result:
ok found '3966939.8951656', expected '3966939.8951656', error '0.0000000'
Test #28:
score: 0
Accepted
time: 3ms
memory: 3976kb
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.93580112
result:
ok found '3964869.9358011', expected '3964869.9358011', error '0.0000000'
Test #29:
score: 0
Accepted
time: 4ms
memory: 4136kb
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.52137019
result:
ok found '3969745.5213702', expected '3969745.5213702', error '0.0000000'
Test #30:
score: 0
Accepted
time: 7ms
memory: 5972kb
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.17267507
result:
ok found '3978880.1726751', expected '3978880.1726751', error '0.0000000'
Test #31:
score: 0
Accepted
time: 6ms
memory: 5972kb
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.80252369
result:
ok found '3982178.8025237', expected '3982178.8025237', error '0.0000000'
Test #32:
score: 0
Accepted
time: 12ms
memory: 5748kb
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.68587371
result:
ok found '3982215.6858737', expected '3982215.6858737', error '0.0000000'
Test #33:
score: 0
Accepted
time: 0ms
memory: 5852kb
input:
3 0 0 1 0 0 1
output:
3.41421356
result:
ok found '3.4142136', expected '3.4142136', error '0.0000000'
Test #34:
score: 0
Accepted
time: 0ms
memory: 5920kb
input:
4 0 0 0 1 1 1 1 0
output:
4.00000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #35:
score: 0
Accepted
time: 1ms
memory: 5964kb
input:
4 0 0 0 3 1 2 1 1
output:
6.82842712
result:
ok found '6.8284271', expected '6.8284271', error '0.0000000'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3948kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
9.22677276
result:
ok found '9.2267728', expected '9.2267728', error '0.0000000'
Test #37:
score: 0
Accepted
time: 0ms
memory: 5920kb
input:
5 0 0 1000000000 0 1000000000 500000000 1000000000 1000000000 0 1000000000
output:
4000000000.00000000
result:
ok found '4000000000.0000000', expected '4000000000.0000000', error '0.0000000'
Test #38:
score: 0
Accepted
time: 0ms
memory: 5916kb
input:
5 0 0 1000000000 0 1000000000 499999999 1000000000 1000000000 0 1000000000
output:
4000000000.00000000
result:
ok found '4000000000.0000000', expected '4000000000.0000000', error '0.0000000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
5 0 0 999999999 0 1000000000 50000000 999999999 1000000000 0 1000000000
output:
3999999998.00000001
result:
ok found '3999999998.0000000', expected '3999999998.0000000', error '0.0000000'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
3 0 0 0 0 0 0
output:
0.00000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #41:
score: 0
Accepted
time: 0ms
memory: 5868kb
input:
8 0 0 2 2 3 1 2 0 1 1 2 2 4 0 2 -2
output:
11.31370850
result:
ok found '11.3137085', expected '11.3137085', error '0.0000000'
Test #42:
score: 0
Accepted
time: 0ms
memory: 5920kb
input:
8 0 0 1 0 1 1 0 1 -1 -1 2 -1 2 2 -1 2
output:
12.00000000
result:
ok found '12.0000000', expected '12.0000000', error '0.0000000'
Test #43:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 0 0 1000000000 1000000000 -1000000000 -999999999
output:
5656854248.07816663
result:
ok found '5656854248.0781670', expected '5656854248.0781670', error '0.0000000'
Test #44:
score: 0
Accepted
time: 4ms
memory: 4420kb
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.45835632
result:
ok found '6283185291.4583559', expected '6283185291.4583521', error '0.0000000'
Test #45:
score: 0
Accepted
time: 13ms
memory: 5728kb
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.49227082
result:
ok found '6283185299.4922705', expected '6283185299.4922733', error '0.0000000'