QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#424977 | #8708. Portal | Matutino | 21 | 13ms | 3964kb | C++14 | 1.7kb | 2024-05-29 20:21:10 | 2024-05-29 20:21:10 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define reg register
inline int read(){
int k=1,x=0;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
return k*x;
}
const int N=5e5+10,INF=1e18;
const long double K=0.5;
int n;
struct Node{
int x,y;
inline Node operator-(const Node &A)const{return {x-A.x,y-A.y};}
inline Node operator*(const int &A){return {A*x,A*y};}
inline int operator*(const Node &A)const{return x*A.x+y*A.y;;}
inline int operator^(const Node &A)const{return x*A.y-y*A.x;}
inline int abs(){return x*x+y*y;}
}A,B,C,O;
inline int cabs(reg int x){return x<0?-x:x;}
inline Node gcd(reg Node p1,reg Node p2){
reg int x=std::__gcd(cabs(p1.x),cabs(p2.x)),y=std::__gcd(p1.y,p2.y);
return {x,y};
}
inline long double theta(reg Node p1,reg Node p2){
reg int dot=cabs(p1*p2);
return 1.0L*dot/sqrtl(p1.abs())/sqrtl(p2.abs());
}
inline void trans(reg Node &A,reg Node &B){
if (A.abs()<B.abs()) std::swap(A,B);
reg int k=roundl(1.0L*(A*B)/B.abs());
A=A-B*k; if (A.y<0) A.x=-A.x,A.y=-A.y;
}
signed main(){
n=read(); if (n<=2) return puts("-1"),0;
O.x=read(),O.y=read();
for (reg int i=1;i<n;i++){
C.x=read(),C.y=read(),C=C-O;
if (C.y<0) C.x=-C.x,C.y=-C.y;
if (!A.abs()) A=C; else if ((A^C)==0) A=gcd(A,C);
else if (!B.abs()) B=C; else if ((B^C)==0) B=gcd(B,C);
else{
while (A.abs()&&B.abs()&&C.abs()){
if (theta(A,B)>K) trans(A,B);
else if (theta(C,B)>K) trans(C,B);
else if (theta(A,C)>K) trans(A,C);
else assert(0);
}
if (!A.abs()) std::swap(A,C);
if (!B.abs()) std::swap(B,C);
}
}
reg int ans=cabs(A^B); printf("%lld\n",ans?ans:-1);
return 0;
}
詳細信息
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 1ms
memory: 3736kb
input:
1 1 -1
output:
-1
result:
ok single line: '-1'
Test #2:
score: 1
Accepted
time: 0ms
memory: 3640kb
input:
2 -455833 -283524 427847 159281
output:
-1
result:
ok single line: '-1'
Test #3:
score: 1
Accepted
time: 1ms
memory: 3652kb
input:
2 52420 -46322 -192914 87067
output:
-1
result:
ok single line: '-1'
Test #4:
score: 1
Accepted
time: 1ms
memory: 3528kb
input:
2 52446 -20773 179773 174566
output:
-1
result:
ok single line: '-1'
Test #5:
score: 1
Accepted
time: 0ms
memory: 3556kb
input:
2 -229012 -260770 -174790 -69382
output:
-1
result:
ok single line: '-1'
Test #6:
score: 1
Accepted
time: 0ms
memory: 3660kb
input:
2 -127294 418312 211124 37002
output:
-1
result:
ok single line: '-1'
Test #7:
score: 1
Accepted
time: 0ms
memory: 3776kb
input:
2 -129173 516840 46821 -187136
output:
-1
result:
ok single line: '-1'
Test #8:
score: 1
Accepted
time: 0ms
memory: 3652kb
input:
2 -90088 -7423 234488 19625
output:
-1
result:
ok single line: '-1'
Test #9:
score: 1
Accepted
time: 0ms
memory: 3716kb
input:
2 -48105 256695 15135 -80585
output:
-1
result:
ok single line: '-1'
Test #10:
score: 1
Accepted
time: 1ms
memory: 3504kb
input:
2 -251318 79061 182792 -129183
output:
-1
result:
ok single line: '-1'
Test #11:
score: 1
Accepted
time: 0ms
memory: 3736kb
input:
2 784850 417677 -217245 -460999
output:
-1
result:
ok single line: '-1'
Test #12:
score: 1
Accepted
time: 0ms
memory: 3712kb
input:
2 31270 410692 713271 917276
output:
-1
result:
ok single line: '-1'
Test #13:
score: 1
Accepted
time: 0ms
memory: 3660kb
input:
1 230862 -785444
output:
-1
result:
ok single line: '-1'
Test #14:
score: 1
Accepted
time: 0ms
memory: 3740kb
input:
2 222814 -279784 -73657 59849
output:
-1
result:
ok single line: '-1'
Test #15:
score: 1
Accepted
time: 0ms
memory: 3672kb
input:
2 72171 -104186 201480 105502
output:
-1
result:
ok single line: '-1'
Test #16:
score: 1
Accepted
time: 0ms
memory: 3532kb
input:
2 -17727 -27151 69235 15029
output:
-1
result:
ok single line: '-1'
Test #17:
score: 1
Accepted
time: 0ms
memory: 3524kb
input:
2 -44049 96618 173806 -21489
output:
-1
result:
ok single line: '-1'
Test #18:
score: 1
Accepted
time: 0ms
memory: 3528kb
input:
2 -81268 -53452 329866 -163275
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #19:
score: 10
Accepted
time: 1ms
memory: 3832kb
input:
3 1 1 1 3 3 2
output:
4
result:
ok single line: '4'
Test #20:
score: 10
Accepted
time: 0ms
memory: 3716kb
input:
3 123741 -122828 207774 110184 -33847 97305
output:
55218331445
result:
ok single line: '55218331445'
Test #21:
score: 10
Accepted
time: 0ms
memory: 3716kb
input:
3 -66381 27989 200580 40286 300930 -238824
output:
75745488660
result:
ok single line: '75745488660'
Test #22:
score: 10
Accepted
time: 0ms
memory: 3780kb
input:
3 -212612 305891 -228367 216399 56731 149417
output:
26569291626
result:
ok single line: '26569291626'
Test #23:
score: 10
Accepted
time: 0ms
memory: 3832kb
input:
3 58252 388020 34720 -409605 79321 85296
output:
23928862293
result:
ok single line: '23928862293'
Test #24:
score: 10
Accepted
time: 0ms
memory: 3808kb
input:
3 19556 -29968 -52219 72940 153159 -166846
output:
3924399074
result:
ok single line: '3924399074'
Test #25:
score: 10
Accepted
time: 0ms
memory: 3964kb
input:
3 201002 729262 -242878 -881858 183722 666542
output:
-1
result:
ok single line: '-1'
Test #26:
score: 10
Accepted
time: 1ms
memory: 3868kb
input:
3 -425251 245407 695099 -401393 18815 -10961
output:
-1
result:
ok single line: '-1'
Test #27:
score: 10
Accepted
time: 0ms
memory: 3904kb
input:
3 -74800 392658 -48320 253638 -13280 69678
output:
-1
result:
ok single line: '-1'
Test #28:
score: 10
Accepted
time: 0ms
memory: 3844kb
input:
3 376570 -515419 -67488 -129024 -72636 -138852
output:
6353363484
result:
ok single line: '6353363484'
Test #29:
score: 10
Accepted
time: 1ms
memory: 3720kb
input:
3 -365409 -46168 130463 -388367 -745599 -94238
output:
153937204850
result:
ok single line: '153937204850'
Test #30:
score: 10
Accepted
time: 1ms
memory: 3868kb
input:
3 4925 198059 583262 -155627 573812 -153107
output:
1884923460
result:
ok single line: '1884923460'
Test #31:
score: 10
Accepted
time: 0ms
memory: 3656kb
input:
1 -785465 814199
output:
-1
result:
ok single line: '-1'
Test #32:
score: 10
Accepted
time: 0ms
memory: 3868kb
input:
3 107518 -84340 137659 -15241 359437 347683
output:
4385745738
result:
ok single line: '4385745738'
Test #33:
score: 10
Accepted
time: 0ms
memory: 3832kb
input:
3 -203959 7059 -34097 -218222 96949 -293501
output:
16735132428
result:
ok single line: '16735132428'
Test #34:
score: 10
Accepted
time: 0ms
memory: 3876kb
input:
3 18005 283441 106422 -61165 137635 -175433
output:
652953322
result:
ok single line: '652953322'
Test #35:
score: 10
Accepted
time: 0ms
memory: 3868kb
input:
3 -233201 -63834 105532 -12105 337350 41702
output:
6234493209
result:
ok single line: '6234493209'
Test #36:
score: 10
Accepted
time: 0ms
memory: 3932kb
input:
3 36748 -26399 119775 -223323 224245 -89339
output:
31696939848
result:
ok single line: '31696939848'
Test #37:
score: 10
Accepted
time: 0ms
memory: 3872kb
input:
3 1000000 -110976 -1000000 -1000000 715820 1000000
output:
2474594840320
result:
ok single line: '2474594840320'
Test #38:
score: 10
Accepted
time: 0ms
memory: 3832kb
input:
3 48920 1000000 1000000 -680401 -1000000 -1000000
output:
3664766216920
result:
ok single line: '3664766216920'
Test #39:
score: 10
Accepted
time: 0ms
memory: 3872kb
input:
3 196198 1000000 1000000 -520790 -1000000 -1000000
output:
3426769956420
result:
ok single line: '3426769956420'
Subtask #3:
score: 10
Accepted
Test #40:
score: 10
Accepted
time: 8ms
memory: 3716kb
input:
99840 -359536 735499 -710626 400619 -468266 -282389 -192706 43659 204034 -543669 -100576 -749013 -118006 -283125 -341276 405771 560934 835595 -923936 506603 239724 956299 -680746 -737237 286204 982795 -847576 -282389 -949666 986475 996684 -429589 672984 -133717 140954 696491 -879116 -442837 985064 7...
output:
610880
result:
ok single line: '610880'
Test #41:
score: 10
Accepted
time: 10ms
memory: 3924kb
input:
99680 231534 501002 -604126 79487 -337934 -601948 -869810 434312 -819518 524087 598310 79487 161938 -480538 463182 827612 233566 807092 -51422 666872 155334 -561763 -819518 -419833 290970 947312 -679818 -16273 804558 435167 -387210 223982 161938 223982 35954 373607 -854570 -459163 831482 771182 5251...
output:
434340
result:
ok single line: '434340'
Test #42:
score: 10
Accepted
time: 6ms
memory: 3844kb
input:
99940 -366859 734803 -722883 -352755 266497 350263 892977 -547983 229061 -550941 -253023 -216687 187041 219125 907493 920171 445273 133343 965557 991163 102237 -66815 434577 732831 239757 -263029 -746567 -527277 -350051 879745 -943679 -528263 -928399 -528263 -867279 66295 -696907 -722505 -247675 465...
output:
753304
result:
ok single line: '753304'
Test #43:
score: 10
Accepted
time: 13ms
memory: 3852kb
input:
99940 629940 252040 422661 -727640 847455 297570 -129230 -330430 -539523 962465 267415 639045 -230737 382350 626528 -730 -940433 -799860 -667473 962465 -941286 675155 -880723 467915 727182 -864230 -936168 -94145 608615 697135 -668326 -963925 -947257 201800 -84021 -386950 -882429 735600 -606057 83922...
output:
669605
result:
ok single line: '669605'
Test #44:
score: 10
Accepted
time: 10ms
memory: 3848kb
input:
99831 758237 -429818 616877 504517 482027 -525398 -877633 -183173 773117 659227 89567 -748958 -14593 -305483 -586543 960547 41207 979582 -300103 -4568 493187 778297 -778123 229522 -338233 -273488 96077 -235823 462497 218992 752657 -429818 41207 188617 419717 389902 -245233 478597 878207 229522 -6655...
output:
376650
result:
ok single line: '376650'
Test #45:
score: 10
Accepted
time: 6ms
memory: 3832kb
input:
100000 -185103 330730 640566 330730 -197028 330730 -296469 330730 950535 330730 -436833 330730 -331893 330730 -130545 330730 236349 330730 -462267 330730 -796788 330730 782343 330730 977130 330730 210285 330730 -99909 330730 979830 330730 206793 330730 346842 330730 591111 330730 444690 330730 96783...
output:
-1
result:
ok single line: '-1'
Test #46:
score: 10
Accepted
time: 6ms
memory: 3848kb
input:
100000 897386 -498167 294216 -498167 -416934 -498167 407176 -498167 423246 -498167 -806934 -498167 -106964 -498167 185376 -498167 -17724 -498167 83516 -498167 481156 -498167 795446 -498167 134076 -498167 -338814 -498167 279526 -498167 970276 -498167 844856 -498167 -37134 -498167 -430634 -498167 -954...
output:
-1
result:
ok single line: '-1'
Test #47:
score: 10
Accepted
time: 3ms
memory: 3924kb
input:
100000 302722 467192 -710129 467192 735336 467192 -255381 467192 -822213 467192 -158389 467192 -193270 467192 358540 467192 -219100 467192 558733 467192 -507675 467192 -695590 467192 -409213 467192 -714518 467192 336567 467192 -533925 467192 -773689 467192 -968688 467192 62384 467192 876526 467192 6...
output:
-1
result:
ok single line: '-1'
Test #48:
score: 10
Accepted
time: 10ms
memory: 3860kb
input:
100000 672106 221171 672106 883430 672106 288290 672106 -658799 141374 -131948 141374 158602 141374 309649 141374 650353 141374 642956 141374 -768194 141374 -718417 672106 249667 672106 784734 141374 470511 141374 98035 672106 998389 672106 352965 141374 898640 672106 -536287 672106 -578615 141374 -...
output:
6899516
result:
ok single line: '6899516'
Test #49:
score: 10
Accepted
time: 9ms
memory: 3784kb
input:
100000 -816116 922009 315232 922009 -249356 922009 610000 949351 490680 949351 582100 949351 292220 922009 -987840 949351 595672 922009 -937660 922009 254856 922009 -13192 949351 583064 922009 -350928 922009 -646536 949351 -965832 922009 -193972 949351 -725520 922009 -820104 922009 315472 949351 670...
output:
109368
result:
ok single line: '109368'
Test #50:
score: 10
Accepted
time: 9ms
memory: 3832kb
input:
100000 -400087 361704 168413 -522429 259093 -522429 -133567 361704 -63837 -522429 507753 -522429 327713 361704 -564507 361704 -367307 361704 -783337 361704 -9157 -522429 -827827 -522429 725203 361704 414713 -522429 -125927 361704 877363 361704 812293 361704 -537707 -522429 910523 361704 634733 -5224...
output:
8841330
result:
ok single line: '8841330'
Test #51:
score: 10
Accepted
time: 0ms
memory: 3652kb
input:
1 393683 -129821
output:
-1
result:
ok single line: '-1'
Test #52:
score: 10
Accepted
time: 13ms
memory: 3856kb
input:
99540 40621 884068 577951 239764 -786692 884068 -889682 -915438 820492 -309724 -618176 881224 -464684 -8446 -336083 -615316 -278327 918718 773440 -147292 100609 -406310 594181 -347808 71233 39452 374938 -406310 498904 -276194 877597 797536 259045 305700 853963 605276 -670709 615112 -336083 784766 11...
output:
6
result:
ok single line: '6'
Test #53:
score: 10
Accepted
time: 13ms
memory: 3924kb
input:
99802 605960 -462294 118320 -783465 993870 91908 -864144 -429162 324342 290253 123132 695739 -723136 -925983 -762138 -997044 -580284 -224673 -955872 150849 552280 -842922 993870 -496248 882382 -536550 748448 -118500 936372 -155847 486570 -92055 -545100 -168126 865686 -500748 -362208 740640 -133172 -...
output:
6
result:
ok single line: '6'
Test #54:
score: 10
Accepted
time: 13ms
memory: 3832kb
input:
99969 -999614 -981865 648284 413937 -434763 -919276 739858 -950234 320831 -321652 98406 637373 579061 -919276 -744205 -203204 863982 385671 -35049 -919276 -998529 913303 -742903 413937 620942 -244930 -97328 59939 -256172 769281 710997 -713338 -254653 202615 508970 -919276 289800 -197147 745066 -1971...
output:
146041
result:
ok single line: '146041'
Test #55:
score: 10
Accepted
time: 12ms
memory: 3884kb
input:
99944 -998018 -997121 573972 520015 -31738 362215 409752 82831 -583898 -594737 -470848 738151 967267 -565553 140217 -256889 906577 -296009 -564858 -340937 562667 -389249 156877 82831 -226898 352183 822087 631591 955367 -429545 975597 951175 488887 152239 -188818 502783 -813568 -943457 236012 240223 ...
output:
14280
result:
ok single line: '14280'
Test #56:
score: 10
Accepted
time: 12ms
memory: 3964kb
input:
99960 -997576 -997846 -800914 304194 -415036 522634 14204 507584 -409780 -266416 -351088 449964 -613012 694204 -408904 -225996 656750 247434 879254 -651266 -186838 949194 -788212 928984 616454 -118496 76400 752684 -226258 683884 -351088 -997846 -630532 16524 60194 -904106 -925306 973274 -398830 -615...
output:
188340
result:
ok single line: '188340'
Test #57:
score: 10
Accepted
time: 12ms
memory: 3812kb
input:
99544 -995276 -991700 -297341 -757684 333499 596428 334024 13092 -506186 893492 527434 -872988 -69176 536220 -191606 -596940 -36836 998004 816394 416372 133159 -684980 550009 -991700 281734 249380 -114851 -523100 -607931 787276 595999 248812 -872741 -527644 -739811 -831524 -309731 -680436 -401711 19...
output:
59640
result:
ok single line: '59640'
Test #58:
score: 10
Accepted
time: 13ms
memory: 3848kb
input:
99864 -990863 -998600 754487 300100 -154703 630880 377277 73660 -254533 -566255 -555363 -202175 467727 -607880 425517 -842645 -816663 -465800 -555363 331735 -475633 -4595 67737 436630 -255873 -455810 688827 -939770 -795893 -924785 665377 212410 -282003 73660 -818003 431635 67067 891730 -826043 -3353...
output:
371850
result:
ok single line: '371850'
Subtask #4:
score: 0
Wrong Answer
Test #59:
score: 29
Accepted
time: 0ms
memory: 3784kb
input:
5 0 0 1 0 -1 0 0 1 0 -1
output:
1
result:
ok single line: '1'
Test #60:
score: 29
Accepted
time: 0ms
memory: 3780kb
input:
100 -30 -13 -22 -19 32 9 -18 -11 50 19 16 5 -50 -17 -46 -21 10 -1 -56 -19 2 -11 -24 -15 -4 -11 -8 -11 4 7 -8 -5 34 9 18 7 20 1 -12 -11 -30 -23 -42 -13 -24 -3 16 11 -16 -7 -24 -21 2 -9 28 11 6 -9 -22 -11 4 -7 28 7 -36 -15 -20 -21 4 11 -8 5 20 5 30 21 58 19 4 -1 -46 -19 -6 3 2 11 46 15 18 -1 -24 -7 -2...
output:
4
result:
ok single line: '4'
Test #61:
score: 0
Wrong Answer
time: 0ms
memory: 3964kb
input:
100 66 27 38 -18 -39 -35 -4 9 -18 -24 24 26 17 6 -4 -26 -46 -6 52 1 17 -15 73 26 31 -10 -46 -27 -4 23 17 -29 -74 -37 -11 -39 -4 2 -11 10 3 -34 3 -41 -39 0 10 -14 31 -3 -18 -10 -25 -30 10 0 -53 -33 -18 -31 38 31 10 -35 24 5 52 22 -60 -32 -11 -32 17 13 -81 -36 3 29 -18 -45 -67 -31 45 23 31 -17 45 30 -...
output:
7
result:
wrong answer 1st lines differ - expected: '49', found: '7'
Subtask #5:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #97:
score: 15
Accepted
time: 1ms
memory: 3944kb
input:
2000 -141033 500883 -457875 317099 570107 -451327 -258775 83073 -48988 -181339 184246 148615 322139 -358663 205746 -28713 -246818 493221 315791 -439181 243789 -493721 -152335 -120605 -290252 397465 359491 -136925 321141 -96245 -410156 465995 192919 -87583 464977 -450703 99537 240803 -279989 264903 -...
output:
19966
result:
ok single line: '19966'
Test #98:
score: 15
Accepted
time: 0ms
memory: 3876kb
input:
2000 -135598 -90332 173830 142382 -5414 25496 -82528 -67798 40478 -10214 385764 525926 115398 169908 251308 294282 263590 294314 -531578 -666220 442932 537116 -371396 -521102 -245894 -230144 -429180 -568306 23432 -73138 177504 290528 -331520 -358256 169528 111726 17898 170554 409940 496694 13828 -53...
output:
5972
result:
ok single line: '5972'
Test #99:
score: 15
Accepted
time: 1ms
memory: 3912kb
input:
999 358449 23473 312882 20485 244806 16021 -99966 -6587 -527088 -34595 214611 14041 351312 23005 -383250 -25163 541266 35461 499542 32725 350763 22969 -3342 -251 -505677 -33191 91635 5977 23010 1477 186612 12205 236571 15481 -250392 -16451 -35733 -2375 353508 23149 -474384 -31139 607695 39817 369978...
output:
-1
result:
ok single line: '-1'
Test #100:
score: 15
Accepted
time: 1ms
memory: 3736kb
input:
999 184536 -196295 -436851 464755 102474 -108995 459909 -489245 -275688 293305 34794 -36995 -390744 415705 -133983 142555 445527 -473945 -352251 374755 -385245 409855 -124254 132205 172692 -183695 -133560 142105 126162 -134195 -431775 459355 371079 -394745 313551 -333545 -372132 395905 308898 -32859...
output:
-1
result:
ok single line: '-1'
Test #101:
score: 15
Accepted
time: 1ms
memory: 3912kb
input:
999 319017 -174498 336878 -184271 -69208 37927 522590 -285887 -523895 286718 -24582 13509 502874 -275099 181747 -99388 -91309 50020 -462362 253049 -138002 75569 -283222 155029 126680 -69257 331472 -181313 524922 -287163 -431039 235910 -156393 85632 -264778 144937 434504 -237689 473830 -259207 450881...
output:
-1
result:
ok single line: '-1'
Test #102:
score: 15
Accepted
time: 1ms
memory: 3784kb
input:
1000 -17417 -44014 -67007 -169294 -140537 -355054 244555 617810 -51275 -129550 328345 829490 293461 741362 56797 143474 -304013 -768046 184705 466610 359809 908978 -265025 -669550 264733 668786 -243479 -615118 -203123 -513166 -332057 -838894 -206543 -521806 -60851 -153742 -178841 -451822 256183 6471...
output:
495647892
result:
ok single line: '495647892'
Test #103:
score: 15
Accepted
time: 0ms
memory: 3872kb
input:
1000 56959 91431 -84971 -136404 -331591 -532294 5659 9081 -221771 -356004 -256921 -412429 -188901 -303239 -231461 -371559 316499 508061 -217971 -349904 -257871 -413954 -70721 -113529 242779 389721 203449 326586 -157171 -252304 15349 24636 -35001 -56189 -285231 -457874 67599 108511 367419 589801 -236...
output:
227636110
result:
ok single line: '227636110'
Test #104:
score: 0
Wrong Answer
time: 1ms
memory: 3928kb
input:
1000 26329 -26297 -105751 105783 333129 -333097 387209 -387177 329 -297 -224571 224603 -68311 68343 291009 -290977 -337931 337963 -496011 496043 462089 -462057 429849 -429817 -130711 130743 489909 -489877 119149 -119117 -200131 200163 -506151 506183 457149 -457117 102249 -102217 261629 -261597 -3506...
output:
1040
result:
wrong answer 1st lines differ - expected: '261614080', found: '1040'
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%