QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86617#5373. 投影对称tricyzhkx30 2ms3660kbC++141.6kb2023-03-10 13:58:212023-03-10 13:58:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-10 13:58:24]
  • 评测
  • 测评结果:30
  • 用时:2ms
  • 内存:3660kb
  • [2023-03-10 13:58:21]
  • 提交

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%