QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100653#5373. 投影对称zhouhuanyi50 324ms3600kbC++112.1kb2023-04-27 15:07:392023-04-27 15:07:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-27 15:07:41]
  • 评测
  • 测评结果:50
  • 用时:324ms
  • 内存:3600kb
  • [2023-04-27 15:07:39]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
#include<algorithm>
#define N 2000
#define eps 1e-9
#define inf 1e9
using namespace std;
int read()
{
    char c=0;
    int sum=0,f=1;
    while (c!='-'&&(c<'0'||c>'9')) c=getchar();
    if (c=='-') c=getchar(),f=-1;
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum*f;
}
__float128 abs(__float128 x)
{
    return (x>0)?x:-x;
}
struct reads
{
    int x,y;
};
reads st[N+1],tong[N+1];
__float128 get(__float128 a,__float128 b)
{
    if (abs(a)<eps) return -inf;
    return b/a;
}
struct rds
{
    __float128 a,b;
    bool operator < (const rds &t)const
    {
        return get(a,b)<get(t.a,t.b);
    }
};
set<rds>s;
int n,length;
bool used[N+1];
__float128 sx,sy,delta[N+1];
int main()
{
    bool op;
    __float128 a,b,ds;
    n=read();
    for (int i=1;i<=n;++i) st[i].x=read(),st[i].y=read(),sx+=st[i].x,sy+=st[i].y;
    sx/=n,sy/=n;
    for (int i=1;i<=n;++i)
	if (!used[i])
	{
	    if (abs(st[i].x-sx)<eps&&abs(st[i].y-sy)<eps)
	    {
		used[i]=1;
		break;
	    }
	    for (int j=i+1;j<=n;++j)
		if (!used[j]&&abs(st[i].x+st[j].x-sx*2)<eps&&abs(st[i].y+st[j].y-sy*2)<eps)
		{
		    used[i]=used[j]=1;
		    break;
		}
	}
    for (int i=1;i<=n;++i)
	if (!used[i])
	    tong[++length]=st[i];
    if (!length)
    {
	puts("-1");
	return 0;
    }
    for (int i=2;i<=length;++i)
    {
	a=tong[1].x+tong[i].x-sx*2,b=tong[1].y+tong[i].y-sy*2;
	for (int j=1;j<=length;++j) delta[j]=tong[j].x*b-tong[j].y*a;
	ds=sx*b-sy*a,sort(delta+1,delta+length+1),op=1;
	for (int j=1;j<=length;++j) op&=(abs(delta[j]+delta[length+1-j]-ds*2)<eps);
	if (op) s.insert((rds){b,-a});
    }
    for (int i=3;i<=length;++i)
    {
	a=tong[2].x+tong[i].x-sx*2,b=tong[2].y+tong[i].y-sy*2;
	for (int j=1;j<=length;++j) delta[j]=tong[j].x*b-tong[j].y*a;
	ds=sx*b-sy*a,sort(delta+1,delta+length+1),op=1;
	for (int j=1;j<=length;++j) op&=(abs(delta[j]+delta[length+1-j]-ds*2)<eps);
	if (op) s.insert((rds){b,-a});
    }
    printf("%d\n",s.size());
    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: 3488kb

input:

3
32650 -45713
899736 648739
381340 196264

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3600kb

input:

3
1 1
1 4
1 5

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

3
1 2
2 1
3 3

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3344kb

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: 3472kb

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: 3332kb

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: 3452kb

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: 3536kb

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: 3524kb

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: 3308kb

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: 3544kb

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: 3552kb

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: 2ms
memory: 3516kb

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: 324ms
memory: 3568kb

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
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #15:

score: 50
Accepted
time: 24ms
memory: 3364kb

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: 2ms
memory: 3464kb

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: 7ms
memory: 3524kb

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: 4ms
memory: 3344kb

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: -50
Time Limit Exceeded

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:


result: