QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424948#8708. PortalMatutino1 1ms3932kbC++141.6kb2024-05-29 20:06:252024-05-29 20:06:26

Judging History

This is the latest submission verdict.

  • [2024-05-29 20:06:26]
  • Judged
  • Verdict: 1
  • Time: 1ms
  • Memory: 3932kb
  • [2024-05-29 20:06:25]
  • 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; 
		}
	}
	printf("%lld\n",cabs(A^B));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

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

input:

1
1 -1

output:

-1

result:

ok single line: '-1'

Test #2:

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

input:

2
-455833 -283524
427847 159281

output:

-1

result:

ok single line: '-1'

Test #3:

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

input:

2
52420 -46322
-192914 87067

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

2
52446 -20773
179773 174566

output:

-1

result:

ok single line: '-1'

Test #5:

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

input:

2
-229012 -260770
-174790 -69382

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

2
-127294 418312
211124 37002

output:

-1

result:

ok single line: '-1'

Test #7:

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

input:

2
-129173 516840
46821 -187136

output:

-1

result:

ok single line: '-1'

Test #8:

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

input:

2
-90088 -7423
234488 19625

output:

-1

result:

ok single line: '-1'

Test #9:

score: 1
Accepted
time: 1ms
memory: 3680kb

input:

2
-48105 256695
15135 -80585

output:

-1

result:

ok single line: '-1'

Test #10:

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

input:

2
-251318 79061
182792 -129183

output:

-1

result:

ok single line: '-1'

Test #11:

score: 1
Accepted
time: 1ms
memory: 3736kb

input:

2
784850 417677
-217245 -460999

output:

-1

result:

ok single line: '-1'

Test #12:

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

input:

2
31270 410692
713271 917276

output:

-1

result:

ok single line: '-1'

Test #13:

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

input:

1
230862 -785444

output:

-1

result:

ok single line: '-1'

Test #14:

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

input:

2
222814 -279784
-73657 59849

output:

-1

result:

ok single line: '-1'

Test #15:

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

input:

2
72171 -104186
201480 105502

output:

-1

result:

ok single line: '-1'

Test #16:

score: 1
Accepted
time: 1ms
memory: 3712kb

input:

2
-17727 -27151
69235 15029

output:

-1

result:

ok single line: '-1'

Test #17:

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

input:

2
-44049 96618
173806 -21489

output:

-1

result:

ok single line: '-1'

Test #18:

score: 1
Accepted
time: 1ms
memory: 3680kb

input:

2
-81268 -53452
329866 -163275

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #19:

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

input:

3
1 1
1 3
3 2

output:

4

result:

ok single line: '4'

Test #20:

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

input:

3
123741 -122828
207774 110184
-33847 97305

output:

55218331445

result:

ok single line: '55218331445'

Test #21:

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

input:

3
-66381 27989
200580 40286
300930 -238824

output:

75745488660

result:

ok single line: '75745488660'

Test #22:

score: 10
Accepted
time: 1ms
memory: 3848kb

input:

3
-212612 305891
-228367 216399
56731 149417

output:

26569291626

result:

ok single line: '26569291626'

Test #23:

score: 10
Accepted
time: 1ms
memory: 3872kb

input:

3
58252 388020
34720 -409605
79321 85296

output:

23928862293

result:

ok single line: '23928862293'

Test #24:

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

input:

3
19556 -29968
-52219 72940
153159 -166846

output:

3924399074

result:

ok single line: '3924399074'

Test #25:

score: 0
Wrong Answer
time: 1ms
memory: 3860kb

input:

3
201002 729262
-242878 -881858
183722 666542

output:

0

result:

wrong answer 1st lines differ - expected: '-1', found: '0'

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

input:

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

output:

1

result:

ok single line: '1'

Test #60:

score: 0
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
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%