QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86617 | #5373. 投影对称 | tricyzhkx | 30 | 2ms | 3660kb | C++14 | 1.6kb | 2023-03-10 13:58:21 | 2023-03-10 13:58:24 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
struct Point{ll x,y;}a[2010];
struct Frac
{
ll x,y;
Frac(ll _x=0,ll _y=1){x=_x;y=_y;if(y<0) x*=-1,y*=-1;else if(!y) x=1;}
Frac operator+(const Frac &a)const{return Frac(x*a.y+y*a.x,y*a.y);}
Frac operator*(ll k)const{return Frac(x*k,y);}
bool operator<(const Frac &a)const{return (lll)x*a.y<(lll)y*a.x;}
bool operator==(const Frac &a)const{return (lll)x*a.y==(lll)y*a.x;}
}b[2010];
bool del[2010];
int main()
{
int n,tn=0;
ll Gx=0,Gy=0;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&a[i].x,&a[i].y);
Gx+=a[i].x;Gy+=a[i].y;
a[i].x*=n;a[i].y*=n;
}
auto find=[&](ll x,ll y)
{
for(int i=1;i<=n;i++)
if(!del[i] && a[i].x==x && a[i].y==y)
return i;
return 0;
};
for(int i=1;i<=n;i++)
if(a[i].x==Gx && a[i].y==Gy)
del[i]=1;
for(int i=1,j;i<=n;i++)
if(!del[i] && (j=find(2*Gx-a[i].x,2*Gy-a[i].y))>0)
del[i]=del[j]=1;
for(int i=1;i<=n;i++)
if(!del[i]) a[++tn]=a[i];
n=tn;
if(!n) return puts("-1"),0;
auto check=[&](Frac k)
{
Frac mid=k.y?Frac(Gx)+k*Gy:Gy;
for(int i=1;i<=n;i++) b[i]=k.y?Frac(a[i].x)+k*a[i].y:a[i].y;
sort(b+1,b+n+1);
bool ok=1;
for(int i=1;i<=n-i+1;i++) ok&=(b[i]+b[n-i+1]==mid*2);
return ok;
};
set<Frac> st;
Frac t;
if(n&1)
{
for(int i=1;i<=n;i++)
if(check(t=Frac(a[i].x-Gx,Gy-a[i].y)))
st.insert(t);
}
else
{
for(int i=2;i<=n;i++)
if(check(t=Frac(a[1].x+a[i].x-2*Gx,2*Gy-a[1].y-a[i].y)))
st.insert(t);
}
cout<<st.size()<<endl;
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: 3632kb
input:
3 32650 -45713 899736 648739 381340 196264
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
3 1 1 1 4 1 5
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
3 1 2 2 1 3 3
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 1 1 2 2 3 3
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #5:
score: 20
Accepted
time: 2ms
memory: 3468kb
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: 0ms
memory: 3544kb
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: 3536kb
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: 2ms
memory: 3540kb
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: 3660kb
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: 2ms
memory: 3568kb
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: -20
Wrong Answer
time: 2ms
memory: 3640kb
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:
0
result:
wrong answer 1st lines differ - expected: '2', found: '0'
Subtask #3:
score: 20
Accepted
Test #13:
score: 20
Accepted
time: 1ms
memory: 3564kb
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: 0ms
memory: 3500kb
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: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%