QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#71950 | #5373. 投影对称 | Crysfly | 100 ✓ | 245ms | 3940kb | C++17 | 2.4kb | 2023-01-12 20:48:46 | 2023-01-12 20:48:49 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db long double
#define eps 1e-7
using namespace std;
const int M=2e3+7;
map<pair<ll,ll>,bool> ma;
ll n,nown,x[M],y[M],cntx,cnty,cntb,ans,gcdsum;
bool del[M],used,used_;
db b[M];
bool check(int cntb){
for(int i=1;i+i<=cntb;i++)
if(fabs(b[i]+b[cntb-i+1]-b[0]-b[0])>=eps)
return 0;
return 1;
}
ll Gcd(ll a,ll b){
if(b==0) return a;
return Gcd(b,a%b);
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&x[i],&y[i]);
cntx+=x[i],cnty+=y[i],x[i]*=n,y[i]*=n;
//珍爱生命,远离double,这样写可以在这里避免产生小数
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(x[i]+x[j]==cntx+cntx && y[i]+y[j]==cnty+cnty)
del[i]=1,del[j]=1;
for(int i=1;i<=n;i++)
if(!del[i]){
nown++;
x[nown]=x[i],y[nown]=y[i];
}
if(!nown) return puts("-1"),0;
n=nown;
if(n%2==0){
//枚举和第一个点的投影对称的投影点
for(int i=2;i<=n;i++){
db midx,midy;
midx=(x[1]+x[i])*0.5;
midy=(y[1]+y[i])*0.5;
if(midx-cntx==0){
if(used) goto js1;
used=1;
//特判掉,不然会寄
for(int j=1;j<=n;j++)
b[j]=x[j];
b[0]=(b[1]+b[i])*0.5;
}else{
gcdsum=Gcd(midy-cnty,midx-cntx);
db k=(db)(midy-cnty)/(midx-cntx);
if(midy-cnty==0 && used_) goto js1;
if(midy-cnty!=0 && ma[make_pair((midy-cnty)/gcdsum,(midx-cntx)/gcdsum)])
goto js1;
if(midy-cnty==0) used_=1;
else ma[make_pair((midy-cnty)/gcdsum,(midx-cntx)/gcdsum)]=1;
for(int j=1;j<=n;j++)
b[j]=y[j]-k*x[j];
b[0]=midy-k*midx;
}
sort(b+1,b+1+n);
if(check(n)) ans++;
js1:;
}
}else{
for(int i=1;i<=n;i++){
cntb=0;
if(x[i]-cntx==0){
//特判掉,不然也会寄
if(used) goto js2;
used=1;
for(int j=1;j<=n;j++)
if(j!=i) b[++cntb]=x[j];
b[0]=x[i];
}else{
gcdsum=Gcd(y[i]-cnty,x[i]-cntx);
db k=(db)(y[i]-cnty)/(x[i]-cntx);
//y=kx+b,b=y-kx
if(y[i]-cnty==0 && used_) goto js2;
if(y[i]-cnty!=0 && ma[make_pair((y[i]-cnty)/gcdsum,(x[i]-cntx)/gcdsum)])
goto js2;
if(y[i]-cnty==0) used_=1;
else ma[make_pair((y[i]-cnty)/gcdsum,(x[i]-cntx)/gcdsum)]=1;
for(int j=1;j<=n;j++)
if(j!=i) b[++cntb]=y[j]-k*x[j];
b[0]=y[i]-k*x[i];
}
sort(b+1,b+1+cntb);
if(check(cntb)) ans++;
js2:;
}
}
printf("%lld",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 2ms
memory: 3556kb
input:
3 32650 -45713 899736 648739 381340 196264
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
3 1 1 1 4 1 5
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
3 1 2 2 1 3 3
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
3 1 1 2 2 3 3
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #5:
score: 20
Accepted
time: 2ms
memory: 3656kb
input:
12 -6191 -122368 -253503 -310480 -320847 -426528 61153 -6320 -23243 -17844 -287319 -279481 -11779 -146876 21749 172 -298495 -328496 -382603 -518068 -68235 -35860 -225275 -365988
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
12 102592 -281444 118934 -562200 577068 -426162 513364 -418859 560726 -145406 303445 -255863 218695 -95862 166296 -288747 535866 -531920 376215 -451743 143794 -175686 460965 -611744
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
12 178870 90855 -19632 -87517 137434 93005 480700 508029 -63786 -185111 351862 348239 552176 593107 50032 -68935 223930 221697 352768 381487 307708 250645 -135262 -270189
output:
2
result:
ok single line: '2'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
10 228246 404422 73521 122097 36225 163914 306832 417600 267539 411011 61089 136036 158098 280493 -9059 12107 236684 293671 139675 149214
output:
5
result:
ok single line: '5'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
12 13308 -110371 -223644 -78203 18140 213941 127936 552677 -40741 11661 139032 360013 -164764 124077 37200 87101 329900 515701 321936 449877 -274561 -214659 306008 318229
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
12 -293352 100783 -348467 56894 -359374 97131 -145994 469332 -287204 118319 -298111 158556 -185151 361841 -461427 -146391 -353226 114667 -335047 18229 -500584 -253882 -311531 197221
output:
-1
result:
ok single line: '-1'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
12 695162 286146 437318 -528096 634662 148396 392662 -402604 319438 -607186 236610 -682190 214282 -619444 625058 277974 115610 -957690 322558 -410776 144178 -627616 516782 69306
output:
2
result:
ok single line: '2'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
6 -100000 100000 -60000 -20000 -20000 20000 20000 60000 60000 -100000 100000 -60000
output:
5
result:
ok single line: '5'
Subtask #3:
score: 20
Accepted
Test #13:
score: 20
Accepted
time: 3ms
memory: 3680kb
input:
1986 -130037 -139562 -244707 -368070 -124449 -171906 -121655 -188078 27969 61170 148227 257334 -54541 -130426 183181 278074 97877 102650 218135 298814 0 -999131 0 999131 0 -997957 0 997957 0 -997214 0 997214 0 -993580 0 993580 0 -992530 0 992530 0 -989565 0 989565 0 -989244 0 989244 0 -988703 0 9887...
output:
5
result:
ok single line: '5'
Test #14:
score: 0
Accepted
time: 6ms
memory: 3676kb
input:
1946 143587 172352 65745 94316 -12097 16280 -221429 -250388 89939 61756 -65745 -94316 0 -9966 0 9966 0 -9961 0 9961 0 -9955 0 9955 0 -9917 0 9917 0 -9866 0 9866 0 -9828 0 9828 0 -9823 0 9823 0 -9819 0 9819 0 -9804 0 9804 0 -9785 0 9785 0 -9727 0 9727 0 -9702 0 9702 0 -9668 0 9668 0 -9653 0 9653 0 -9...
output:
2
result:
ok single line: '2'
Subtask #4:
score: 50
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #15:
score: 50
Accepted
time: 4ms
memory: 3476kb
input:
2000 -178141 -315933 -312601 -473505 90209 -82603 109454 21096 -52261 -139069 -28561 -108265 -49261 -142285 -124816 -266458 -244156 -375622 -306376 -466210 -307396 -442126 -383656 -522322 133109 48817 -146626 -311256 -70486 -172324 -320071 -482259 -411376 -453242 -160696 -325426 -102391 -229603 -282...
output:
-1
result:
ok single line: '-1'
Test #16:
score: 0
Accepted
time: 3ms
memory: 3624kb
input:
15 130122 359297 4326 237953 358 309601 -121470 116609 47502 415457 582312 569057 -424292 81121 263854 337345 -62540 248929 -333854 123073 299212 416737 649178 558081 271672 435457 318816 541313 149844 242465
output:
3
result:
ok single line: '3'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
100 -587294 -358098 780773 -856822 678977 -381452 -776422 317649 -588375 -650040 590048 -40446 845265 435118 460236 -876087 -942777 -467172 873347 -305402 -531 -992517 -490557 173517 113271 152618 -156584 675175 702575 22011 286759 483151 258354 125749 363047 197429 816880 130960 -772125 -171137 666...
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 3ms
memory: 3324kb
input:
100 65580 120159 -63654 -24831 69430 168133 -159095 -229766 -125643 244974 -2809 254540 65671 417484 -55225 474380 11137 312514 11990 131621 14223 502404 -121554 -245235 -88447 91586 -142890 283941 -119269 295448 57448 261571 -102317 -47840 -2147 109126 30079 205588 29317 683806 41959 108652 -103732...
output:
-1
result:
ok single line: '-1'
Test #19:
score: 0
Accepted
time: 236ms
memory: 3716kb
input:
2000 149650 -482294 647442 24768 210466 -466877 111378 -532032 -17134 -409603 560850 -138273 148754 -351364 105746 -366463 376210 -222177 515138 -358751 466194 -195240 307218 -223128 251218 -350297 196258 -496997 505618 -356392 579410 -127103 338818 -92541 293618 -279330 517650 -93402 24050 -316258 ...
output:
4
result:
ok single line: '4'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
12 -359389 174272 -416557 200820 214979 585478 -316065 267142 387379 731396 13995 452834 -646125 81450 -293955 426358 -330805 160998 114487 519156 -265371 413084 -86497 386512
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
100 -169079 -262370 -498832 -697191 556168 460101 663387 371853 583493 193753 134173 517464 973463 593660 -546711 321094 -720979 177091 673031 784343 737287 -838087 -332975 -365377 335099 -731940 -359370 835943 313393 -443363 879546 887402 -286809 212324 773364 -62440 -873171 -973302 -381554 -280841...
output:
0
result:
ok single line: '0'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
100 -238970 -122043 18881 178631 -350613 -24573 -71127 87159 -250042 -110555 16621 292367 -232418 93941 -170928 -39775 56178 327757 -284152 -135599 -316234 62405 -429276 154809 -480890 -22715 -567533 -22285 -705790 -199379 -430319 85383 -17369 319339 -245216 122625 -529735 -148009 -317513 109355 -11...
output:
-1
result:
ok single line: '-1'
Test #23:
score: 0
Accepted
time: 85ms
memory: 3744kb
input:
2000 1497 8396 -408648 -150314 -344016 -125402 -173864 -55690 -282617 -98720 -68620 -21314 -209770 -73686 15770 13954 -310546 -112582 -162604 -55490 -152722 -54598 -181262 -56878 -123190 -40286 -152501 -51912 -57010 -15046 -43090 -8006 -214656 -75642 -79391 -22452 -294124 -105986 28434 17298 -14321 ...
output:
5
result:
ok single line: '5'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
9 35859 427946 -152971 248902 -482961 -33446 133679 522878 322509 701922 113249 490418 -21101 397934 -378331 72306 56289 460406
output:
2
result:
ok single line: '2'
Test #25:
score: 0
Accepted
time: 3ms
memory: 3644kb
input:
100 104957 -722566 219416 927619 -89622 -958984 -381563 51210 -841010 -952853 -814685 -106863 241729 158136 -301851 815014 679474 -28238 146515 -265849 405089 442278 265863 -505430 -421276 415696 -628432 -302154 440867 374627 140306 -93048 120284 64645 -948348 -821073 -229217 -579375 740209 -291471 ...
output:
0
result:
ok single line: '0'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
100 239584 5334 318789 3098 380601 92018 -458365 -415654 286178 18742 -359197 -359654 -363385 -344014 215228 -60034 203 -129694 -239467 -260534 -337873 -295398 -280407 -317262 250146 -19010 -439595 -417358 223725 -41582 288075 29866 -377783 -328438 223499 -57614 -154550 -236138 -127367 -192430 -1860...
output:
-1
result:
ok single line: '-1'
Test #27:
score: 0
Accepted
time: 245ms
memory: 3788kb
input:
2000 140400 -341832 -87140 -464436 382003 -149886 105775 -345582 -211058 -630240 -358828 -656052 -281303 -602802 158638 -311868 17062 -403632 -51683 -480810 -8048 -412332 124921 -314802 -128207 -491490 31912 -339348 13597 -336906 552097 8958 116855 -344382 48229 -375258 -151755 -532794 -20216 -42034...
output:
5
result:
ok single line: '5'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
9 428394 -205989 263210 -405839 388626 38927 483238 -369873 258402 -202349 448278 -328447 518198 -411299 193290 -322987 423586 -2499
output:
3
result:
ok single line: '3'
Test #29:
score: 0
Accepted
time: 3ms
memory: 3508kb
input:
100 -845471 979406 -926190 500997 969691 699524 508728 868811 -642501 -857193 -233426 391337 447226 -663479 -918329 962187 621285 -793263 -315030 -885999 -882787 551768 367251 -807153 -476904 -775042 -39343 869262 -824161 654035 -945467 -370871 554958 -827298 -821207 -980687 702487 -467302 705223 -4...
output:
0
result:
ok single line: '0'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
100 -331184 368752 -303064 595182 -327004 460509 -418544 154774 -346324 384151 -359804 245465 -332984 463684 -323084 478969 -357124 237195 -363904 333744 -325344 511152 -421324 142727 -412484 280453 -437804 111079 -339604 357303 -381764 369759 -455864 -98268 -296104 596622 -300364 529557 -399624 201...
output:
-1
result:
ok single line: '-1'
Test #31:
score: 0
Accepted
time: 227ms
memory: 3940kb
input:
2000 -503901 -282515 183667 -117441 -386221 -490275 -72729 -53769 351703 -127143 282961 -123174 16333 -2928 -368559 251466 -201621 -294975 30223 33717 66227 -348511 18237 -78556 -344339 226476 35597 -67076 -341791 -222910 123749 280460 -172957 -1423 181121 -117294 -159163 -250056 -361639 244326 -129...
output:
3
result:
ok single line: '3'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
9 53258 -211393 154740 -229123 -138020 -364807 -161870 -339881 -15490 -272039 471350 -118365 -424698 -418517 -185720 -314955 456384 -146889
output:
3
result:
ok single line: '3'
Test #33:
score: 0
Accepted
time: 2ms
memory: 3824kb
input:
100 -924551 204327 -694258 980900 12045 191430 715113 816070 129325 -460391 316954 -415689 323858 276128 674229 -735839 -859319 89299 -999969 882918 928307 -42724 -49835 760472 -800762 -738599 -59163 -237822 228683 -50980 253683 302237 -108578 192747 -784651 625948 -135951 -875968 877176 642145 6938...
output:
0
result:
ok single line: '0'
Test #34:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
100 363007 31646 -55617 -558506 10895 -336198 232903 -30970 530203 300811 363743 -47150 237763 -164281 240227 -229615 134467 -258959 186447 -118164 487027 179999 429275 190769 37443 -270963 459947 201489 290507 -154895 24191 -410128 458791 156558 211295 -119004 250431 -101516 412363 16751 358327 -42...
output:
-1
result:
ok single line: '-1'