QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#71950#5373. 投影对称Crysfly100 ✓245ms3940kbC++172.4kb2023-01-12 20:48:462023-01-12 20:48:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-12 20:48:49]
  • 评测
  • 测评结果:100
  • 用时:245ms
  • 内存:3940kb
  • [2023-01-12 20:48:46]
  • 提交

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'