QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424955#8708. PortalMatutino11 0ms3916kbC++141.6kb2024-05-29 20:09:412024-05-29 20:09:42

Judging History

This is the latest submission verdict.

  • [2024-05-29 20:09:42]
  • Judged
  • Verdict: 11
  • Time: 0ms
  • Memory: 3916kb
  • [2024-05-29 20:09:41]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
#define reg register
inline int read(){
	int k=1,x=0;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
	return k*x;
}
const int N=5e5+10,INF=1e18;
const long double K=sqrtl(3)/2;
int n;
struct Node{
	int x,y;
	inline Node operator-(const Node &A)const{return {x-A.x,y-A.y};}
	inline Node operator*(const int &A){return {A*x,A*y};}
	inline int operator*(const Node &A)const{return x*A.x+y*A.y;;}
	inline int operator^(const Node &A)const{return x*A.y-y*A.x;}
	inline int abs(){return x*x+y*y;}
}A,B,C,O;
inline int cabs(reg int x){return x<0?-x:x;}
inline Node gcd(reg Node p1,reg Node p2){
	reg int x=std::__gcd(cabs(p1.x),cabs(p2.x)),y=std::__gcd(p1.y,p2.y);
	return {x,y};
}
inline long double theta(reg Node p1,reg Node p2){
	reg int dot=cabs(p1*p2);
	return 1.0L*dot/sqrtl(p1.abs())/sqrtl(p2.abs());
}
inline void trans(reg Node &A,reg Node &B){
	if (A.abs()<B.abs()) std::swap(A,B);
	reg int k=roundl(1.0L*(A*B)/sqrtl(B.abs()));
	A=A-B*k;
}
signed main(){
	n=read(); if (n<=2) return puts("-1"),0;
	O.x=read(),O.y=read();
	for (reg int i=1;i<n;i++){
		C.x=read(),C.y=read(),C=C-O;
		if (C.y<0) C.x=-C.x,C.y=-C.y;
		if (!A.abs()) A=C; else if (A*C==0) A=gcd(A,C); else if (!B.abs()) B=C;
		else{
			while (A.abs()&&B.abs()&&C.abs()){
				if (theta(A,B)<K) trans(A,B);
				if (theta(C,B)<K) trans(C,B);
				if (theta(A,C)<K) trans(A,C); 
			}
			if (!A.abs()) A=C; 
			if (!B.abs()) B=C; 
		}
	}
	reg int ans=cabs(A^B); printf("%lld\n",ans?ans:-1);
	return 0;
}

詳細信息

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 0ms
memory: 3632kb

input:

1
1 -1

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

2
-455833 -283524
427847 159281

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

2
52420 -46322
-192914 87067

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

2
52446 -20773
179773 174566

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

2
-229012 -260770
-174790 -69382

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

2
-127294 418312
211124 37002

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

2
-129173 516840
46821 -187136

output:

-1

result:

ok single line: '-1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

2
-90088 -7423
234488 19625

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

2
-48105 256695
15135 -80585

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

2
-251318 79061
182792 -129183

output:

-1

result:

ok single line: '-1'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

2
784850 417677
-217245 -460999

output:

-1

result:

ok single line: '-1'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

2
31270 410692
713271 917276

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

1
230862 -785444

output:

-1

result:

ok single line: '-1'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

2
222814 -279784
-73657 59849

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

2
72171 -104186
201480 105502

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

2
-17727 -27151
69235 15029

output:

-1

result:

ok single line: '-1'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

2
-44049 96618
173806 -21489

output:

-1

result:

ok single line: '-1'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

2
-81268 -53452
329866 -163275

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #19:

score: 10
Accepted
time: 0ms
memory: 3784kb

input:

3
1 1
1 3
3 2

output:

4

result:

ok single line: '4'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

3
123741 -122828
207774 110184
-33847 97305

output:

55218331445

result:

ok single line: '55218331445'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

3
-66381 27989
200580 40286
300930 -238824

output:

75745488660

result:

ok single line: '75745488660'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

3
-212612 305891
-228367 216399
56731 149417

output:

26569291626

result:

ok single line: '26569291626'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

3
58252 388020
34720 -409605
79321 85296

output:

23928862293

result:

ok single line: '23928862293'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

3
19556 -29968
-52219 72940
153159 -166846

output:

3924399074

result:

ok single line: '3924399074'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

3
201002 729262
-242878 -881858
183722 666542

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

3
-425251 245407
695099 -401393
18815 -10961

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3
-74800 392658
-48320 253638
-13280 69678

output:

-1

result:

ok single line: '-1'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

3
376570 -515419
-67488 -129024
-72636 -138852

output:

6353363484

result:

ok single line: '6353363484'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3
-365409 -46168
130463 -388367
-745599 -94238

output:

153937204850

result:

ok single line: '153937204850'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

3
4925 198059
583262 -155627
573812 -153107

output:

1884923460

result:

ok single line: '1884923460'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

1
-785465 814199

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

3
107518 -84340
137659 -15241
359437 347683

output:

4385745738

result:

ok single line: '4385745738'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

3
-203959 7059
-34097 -218222
96949 -293501

output:

16735132428

result:

ok single line: '16735132428'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

3
18005 283441
106422 -61165
137635 -175433

output:

652953322

result:

ok single line: '652953322'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

3
-233201 -63834
105532 -12105
337350 41702

output:

6234493209

result:

ok single line: '6234493209'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3
36748 -26399
119775 -223323
224245 -89339

output:

31696939848

result:

ok single line: '31696939848'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

3
1000000 -110976
-1000000 -1000000
715820 1000000

output:

2474594840320

result:

ok single line: '2474594840320'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

3
48920 1000000
1000000 -680401
-1000000 -1000000

output:

3664766216920

result:

ok single line: '3664766216920'

Test #39:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

3
196198 1000000
1000000 -520790
-1000000 -1000000

output:

3426769956420

result:

ok single line: '3426769956420'

Subtask #3:

score: 0
Time Limit Exceeded

Test #40:

score: 0
Time Limit Exceeded

input:

99840
-359536 735499
-710626 400619
-468266 -282389
-192706 43659
204034 -543669
-100576 -749013
-118006 -283125
-341276 405771
560934 835595
-923936 506603
239724 956299
-680746 -737237
286204 982795
-847576 -282389
-949666 986475
996684 -429589
672984 -133717
140954 696491
-879116 -442837
985064 7...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #59:

score: 0
Time Limit Exceeded

input:

5
0 0
1 0
-1 0
0 1
0 -1

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #97:

score: 0
Time Limit Exceeded

input:

2000
-141033 500883
-457875 317099
570107 -451327
-258775 83073
-48988 -181339
184246 148615
322139 -358663
205746 -28713
-246818 493221
315791 -439181
243789 -493721
-152335 -120605
-290252 397465
359491 -136925
321141 -96245
-410156 465995
192919 -87583
464977 -450703
99537 240803
-279989 264903
-...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%