QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100653 | #5373. 投影对称 | zhouhuanyi | 50 | 324ms | 3600kb | C++11 | 2.1kb | 2023-04-27 15:07:39 | 2023-04-27 15:07:41 |
Judging History
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;
}
详细
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 ...