This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// yay linear algebra!
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SQDET = 2828432;
bool pr[SQDET];
vector<int> primes;
int test(int x[], int y[], int n, int p) {
// test against the guy with gcd with lowest vp.
pair<int,int> l = {100,0};
for(int i=1;i<n;i++) {
int g = __gcd(x[i],y[i]), c = 0;
while((!(g%p)) && c<100) g/=p, c++;
l=min(l,{c,i});
}
int g = 0;
for(int i=1;i<n;i++) g=__gcd(g,x[i]*y[l.second]-x[l.second]*y[i]);
int c = 0; while(!(g%p)) g/=p,c++;
return c;
}
main() {
fill(pr,pr+SQDET,1);
for(int i=2;i<SQDET;i++) if(pr[i]) {
primes.push_back(i);
for(int j=i*i;j<SQDET;j+=i) pr[j]=0;
}
int n; cin >> n;
int x[n], y[n]; for(int i=0;i<n;i++) cin>>x[i]>>y[i];
for(int i=1;i<n;i++) x[i]-=x[0],y[i]-=y[0];
int g=0; for(int i=2;i<n;i++) g=__gcd(g,x[1]*y[i]-x[i]*y[1]);
if(!g) {cout<<-1; return 0;}
int ans = 1;
for(auto i: primes) if(!(g%i)) {
int k = test(x,y,n,i);
while(k--) ans *= i;
while(!(g%i)) g/=i;
}
if(g>1 && test(x,y,n,g)) ans *= g;
cout << ans;
}
Compilation message (stderr)
Main.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
21 | main() {
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |