QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419290#8708. Portalpaul20081 1ms3944kbC++141.3kb2024-05-23 19:57:562024-05-23 19:57:58

Judging History

This is the latest submission verdict.

  • [2024-05-23 19:57:58]
  • Judged
  • Verdict: 1
  • Time: 1ms
  • Memory: 3944kb
  • [2024-05-23 19:57:56]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e5+5;

int gcd(int x,int y)
{
	if(x>y)
		swap(x,y);

	if(x==0)
		return y;

	return gcd(y%x,x);
}

int lcm(int x,int y)
{
	return x/gcd(x,y)*y;
}

int x[N],y[N],val[N];
map <pair <int,int> ,bool> have;
map <pair <int,int> ,int> res;

pair <int,int> topair(int x,int y)
{
	if(x==0)
		return make_pair(0x3f3f3f3f,0);

	if(y==0)
		return make_pair(0,0);

	int GCD=gcd(abs(x),abs(y));
	x /= GCD, y /= GCD;
	if(x<0)
		x=-x, y=-y;
	return make_pair(x,y);
}

signed main()
{
	int n;
	cin >> n;
	if(n<=2)
	{
		printf("-1\n");
		return 0;
	}

	for(int i=1;i<=n;i++)
		scanf("%lld %lld",&x[i],&y[i]);

	for(int i=1;i<n;i++)
		x[i] -= x[n], y[i] -= y[n];
	n--;

	for(int i=1;i<=n;i++)
		have[topair(x[i],y[i])]=true;

	if(have.size()==1)
	{
		printf("-1\n");
		return 0;
	}

	for(int i=1;i<=n;i++)
	{
		int GCD=gcd(abs(x[i]),abs(y[i]));
		for(int j=1;j<=n;j++)
		{
			if(i==j)
				val[j]=0;
			else
				val[j]=abs((x[i]*y[j]-y[i]*x[j])/GCD);
		}

		int t=0;
		for(int j=1;j<=n;j++)
			t=gcd(t,val[j]);

		res[make_pair(y[i]/GCD,x[i]/GCD)]=t;
	}

	long long ans=1;
	for(auto x:res)
		ans=lcm(ans,x.second);
	printf("%lld\n",ans);
	return 0;
}

詳細信息

Subtask #1:

score: 1
Accepted

Test #1:

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

input:

1
1 -1

output:

-1

result:

ok single line: '-1'

Test #2:

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

input:

2
-455833 -283524
427847 159281

output:

-1

result:

ok single line: '-1'

Test #3:

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

input:

2
52420 -46322
-192914 87067

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

2
52446 -20773
179773 174566

output:

-1

result:

ok single line: '-1'

Test #5:

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

input:

2
-229012 -260770
-174790 -69382

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

2
-127294 418312
211124 37002

output:

-1

result:

ok single line: '-1'

Test #7:

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

input:

2
-129173 516840
46821 -187136

output:

-1

result:

ok single line: '-1'

Test #8:

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

input:

2
-90088 -7423
234488 19625

output:

-1

result:

ok single line: '-1'

Test #9:

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

input:

2
-48105 256695
15135 -80585

output:

-1

result:

ok single line: '-1'

Test #10:

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

input:

2
-251318 79061
182792 -129183

output:

-1

result:

ok single line: '-1'

Test #11:

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

input:

2
784850 417677
-217245 -460999

output:

-1

result:

ok single line: '-1'

Test #12:

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

input:

2
31270 410692
713271 917276

output:

-1

result:

ok single line: '-1'

Test #13:

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

input:

1
230862 -785444

output:

-1

result:

ok single line: '-1'

Test #14:

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

input:

2
222814 -279784
-73657 59849

output:

-1

result:

ok single line: '-1'

Test #15:

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

input:

2
72171 -104186
201480 105502

output:

-1

result:

ok single line: '-1'

Test #16:

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

input:

2
-17727 -27151
69235 15029

output:

-1

result:

ok single line: '-1'

Test #17:

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

input:

2
-44049 96618
173806 -21489

output:

-1

result:

ok single line: '-1'

Test #18:

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

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

input:

3
1 1
1 3
3 2

output:

4

result:

ok single line: '4'

Test #20:

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

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

input:

3
-212612 305891
-228367 216399
56731 149417

output:

26569291626

result:

ok single line: '26569291626'

Test #23:

score: 0
Wrong Answer
time: 0ms
memory: 3852kb

input:

3
58252 388020
34720 -409605
79321 85296

output:

7976287431

result:

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

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
Wrong Answer

Test #59:

score: 29
Accepted
time: 1ms
memory: 3928kb

input:

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

output:

1

result:

ok single line: '1'

Test #60:

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

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:

2

result:

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

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%