QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#182785#5373. 投影对称Lynkcat#30 14ms5824kbC++202.9kb2023-09-18 15:42:352024-07-04 02:02:13

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:02:13]
  • 评测
  • 测评结果:30
  • 用时:14ms
  • 内存:5824kb
  • [2023-09-18 15:42:35]
  • 提交

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%