QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#424952#8708. PortalMatutino11 0ms3944kbC++141.6kb2024-05-29 20:07:532024-05-29 20:07:54

Judging History

This is the latest submission verdict.

  • [2024-05-29 20:07:54]
  • Judged
  • Verdict: 11
  • Time: 0ms
  • Memory: 3944kb
  • [2024-05-29 20:07:53]
  • 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 _60=acosl(-1)/3;
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)<_60) trans(A,B);
				if (theta(C,B)<_60) trans(C,B);
				if (theta(A,C)<_60) 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: 3616kb

input:

1
1 -1

output:

-1

result:

ok single line: '-1'

Test #2:

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

input:

2
-455833 -283524
427847 159281

output:

-1

result:

ok single line: '-1'

Test #3:

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

input:

2
52420 -46322
-192914 87067

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

2
52446 -20773
179773 174566

output:

-1

result:

ok single line: '-1'

Test #5:

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

input:

2
-229012 -260770
-174790 -69382

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

2
-127294 418312
211124 37002

output:

-1

result:

ok single line: '-1'

Test #7:

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

input:

2
-129173 516840
46821 -187136

output:

-1

result:

ok single line: '-1'

Test #8:

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

input:

2
-90088 -7423
234488 19625

output:

-1

result:

ok single line: '-1'

Test #9:

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

input:

2
-48105 256695
15135 -80585

output:

-1

result:

ok single line: '-1'

Test #10:

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

input:

2
-251318 79061
182792 -129183

output:

-1

result:

ok single line: '-1'

Test #11:

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

input:

2
784850 417677
-217245 -460999

output:

-1

result:

ok single line: '-1'

Test #12:

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

input:

2
31270 410692
713271 917276

output:

-1

result:

ok single line: '-1'

Test #13:

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

input:

1
230862 -785444

output:

-1

result:

ok single line: '-1'

Test #14:

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

input:

2
222814 -279784
-73657 59849

output:

-1

result:

ok single line: '-1'

Test #15:

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

input:

2
72171 -104186
201480 105502

output:

-1

result:

ok single line: '-1'

Test #16:

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

input:

2
-17727 -27151
69235 15029

output:

-1

result:

ok single line: '-1'

Test #17:

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

input:

2
-44049 96618
173806 -21489

output:

-1

result:

ok single line: '-1'

Test #18:

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

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

input:

3
1 1
1 3
3 2

output:

4

result:

ok single line: '4'

Test #20:

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

input:

3
123741 -122828
207774 110184
-33847 97305

output:

55218331445

result:

ok single line: '55218331445'

Test #21:

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

input:

3
-66381 27989
200580 40286
300930 -238824

output:

75745488660

result:

ok single line: '75745488660'

Test #22:

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

input:

3
-212612 305891
-228367 216399
56731 149417

output:

26569291626

result:

ok single line: '26569291626'

Test #23:

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

input:

3
58252 388020
34720 -409605
79321 85296

output:

23928862293

result:

ok single line: '23928862293'

Test #24:

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

input:

3
19556 -29968
-52219 72940
153159 -166846

output:

3924399074

result:

ok single line: '3924399074'

Test #25:

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

input:

3
201002 729262
-242878 -881858
183722 666542

output:

-1

result:

ok single line: '-1'

Test #26:

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

input:

3
-425251 245407
695099 -401393
18815 -10961

output:

-1

result:

ok single line: '-1'

Test #27:

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

input:

3
-74800 392658
-48320 253638
-13280 69678

output:

-1

result:

ok single line: '-1'

Test #28:

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

input:

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

output:

6353363484

result:

ok single line: '6353363484'

Test #29:

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

input:

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

output:

153937204850

result:

ok single line: '153937204850'

Test #30:

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

input:

3
4925 198059
583262 -155627
573812 -153107

output:

1884923460

result:

ok single line: '1884923460'

Test #31:

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

input:

1
-785465 814199

output:

-1

result:

ok single line: '-1'

Test #32:

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

input:

3
107518 -84340
137659 -15241
359437 347683

output:

4385745738

result:

ok single line: '4385745738'

Test #33:

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

input:

3
-203959 7059
-34097 -218222
96949 -293501

output:

16735132428

result:

ok single line: '16735132428'

Test #34:

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

input:

3
18005 283441
106422 -61165
137635 -175433

output:

652953322

result:

ok single line: '652953322'

Test #35:

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

input:

3
-233201 -63834
105532 -12105
337350 41702

output:

6234493209

result:

ok single line: '6234493209'

Test #36:

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

input:

3
36748 -26399
119775 -223323
224245 -89339

output:

31696939848

result:

ok single line: '31696939848'

Test #37:

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

input:

3
1000000 -110976
-1000000 -1000000
715820 1000000

output:

2474594840320

result:

ok single line: '2474594840320'

Test #38:

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

input:

3
48920 1000000
1000000 -680401
-1000000 -1000000

output:

3664766216920

result:

ok single line: '3664766216920'

Test #39:

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

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: 29
Accepted
time: 0ms
memory: 3876kb

input:

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

output:

1

result:

ok single line: '1'

Test #60:

score: -29
Time Limit Exceeded

input:

100
-30 -13
-22 -19
32 9
-18 -11
50 19
16 5
-50 -17
-46 -21
10 -1
-56 -19
2 -11
-24 -15
-4 -11
-8 -11
4 7
-8 -5
34 9
18 7
20 1
-12 -11
-30 -23
-42 -13
-24 -3
16 11
-16 -7
-24 -21
2 -9
28 11
6 -9
-22 -11
4 -7
28 7
-36 -15
-20 -21
4 11
-8 5
20 5
30 21
58 19
4 -1
-46 -19
-6 3
2 11
46 15
18 -1
-24 -7
-2...

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%