QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#182785 | #5373. 投影对称 | Lynkcat# | 30 | 14ms | 5824kb | C++20 | 2.9kb | 2023-09-18 15:42:35 | 2024-07-04 02:02:13 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
#define N 2005
using namespace std;
class point{
public:
int x;
int y;
point(int x_=0,int y_=0):x(x_),y(y_){}
friend const bool operator<(const point& p1,const point& p2){
return (p1.x==p2.x)?p1.y<p2.y:p1.x<p2.x;
};
friend const bool operator==(const point& p1,const point& p2){
return (p1.x==p2.x)&&(p1.y==p2.y);
};
friend const point operator+(const point& p1,const point& p2){
return point(p1.x+p2.x,p1.y+p2.y);
};
friend const point operator-(const point& p1,const point& p2){
return point(p1.x-p2.x,p1.y-p2.y);
};
};
int n,dfn[N],DFN;
point a[N];
int vis[N];
point cz(point x)
{
if (x.x==0) return point(1,0);
if (x.y==0) return point(0,1);
return point(x.y,-x.x);
}
point hj(point nw)
{
if (nw.x<0) nw.y*=-1,nw.x*=-1;
int g=__gcd(abs(nw.x),abs(nw.y));
nw.x/=g,nw.y/=g;
return nw;
}
void BellaKira()
{
cin>>n;
int sx=0,sy=0;
for (int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y,a[i].x*=n,a[i].y*=n,sx+=a[i].x,sy+=a[i].y;
sx/=n,sy/=n;
if (n<=2)
{
cout<<"-1\n";
return;
}
map<point,poly>all;
point mid=point(sx,sy);
// cout<<sx<<" "<<sy<<endl;
for (int i=1;i<=n;i++) vis[i]|=(a[i]==mid);
for (int i=1;i<=n;i++)
if (!vis[i])
{
point x=a[i]-mid;
x=cz(x),x=hj(x);
all[x].push_back(i);
}
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
{
if (vis[i]||vis[j]) continue;
point x=a[i]-mid,y=a[j]-mid;
if ((x+y)==point(0,0))
{
vis[i]=1;vis[j]=1;
continue;
}
point nw=cz(x+y);
// cout<<i<<" "<<j<<" "<<nw.x<<" "<<nw.y<<" "<<(x+y).x<<" "<<(x+y).y<<endl;
if (nw.x<0) nw.y*=-1,nw.x*=-1;
int g=__gcd(abs(nw.x),abs(nw.y));
nw.x/=g,nw.y/=g;
all[nw].push_back(i);
all[nw].push_back(j);
// cout<<i<<" "<<j<<" "<<nw.x<<" "<<nw.y<<endl;
}
int nn=0;
for (int i=1;i<=n;i++) if (!vis[i]) nn++;
if (nn==0)
{
cout<<"-1\n";
return;
}
int ans=0;
for (auto [u,g]:all)
{
DFN++;
int t=0;
for (auto v:g)
{
if (dfn[v]!=DFN) t++,dfn[v]=DFN;
}
// cout<<"?"<<u.x<<" "<<u.y<<" "<<nn<<" "<<g.size()<<" "<<t<<endl;
if (t==nn) ans++;
}
cout<<ans<<'\n';
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
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: 3604kb
input:
3 1 1 1 4 1 5
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
3 1 2 2 1 3 3
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3704kb
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: 1ms
memory: 3668kb
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: 1ms
memory: 3528kb
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: 1ms
memory: 3600kb
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: 1ms
memory: 3644kb
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: 1ms
memory: 3604kb
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: 1ms
memory: 3824kb
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: 1ms
memory: 3860kb
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: 1ms
memory: 3596kb
input:
6 -100000 100000 -60000 -20000 -20000 20000 20000 60000 60000 -100000 100000 -60000
output:
5
result:
ok single line: '5'
Subtask #3:
score: 0
Wrong Answer
Test #13:
score: 20
Accepted
time: 14ms
memory: 5824kb
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: -20
Wrong Answer
time: 7ms
memory: 4712kb
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:
0
result:
wrong answer 1st lines differ - expected: '2', found: '0'
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%