| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1045040 | owoovo | Portal (BOI24_portal) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll __int128_t
#define pll pair<ll,ll>
#define F first
#define S second
using namespace std;
const ll zo=0;
vector<pll> point,vc;
long long n;
ll abs2(ll a){
return max(a,-a);
}
pll fd(pll a){
return max(a,{-a.F,-a.S});
}
void _gcd(pll &a,pll &b){
if(a.F==0||b.F==0)return;
if(a.F<b.F)swap(a,b);
ll g=a.F/b.F;
a.F-=b.F*g;
a.S-=b.S*g;
_gcd(b,a);
return ;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++){
long long x,y;
cin>>x>>y;
point.push_back({x,y});
}
for(int i=1;i<n;i++){
vc.push_back(fd({point[i].F-point[0].F,point[i].S-point[0].S}));
}
pll now={0,0};
vector<ll> s;
for(int i=0;i<n-1;i++){
if(vc[i].F==0){
s.push_back(vc[i].S);
}else{
if(now==make_pair(zo,zo)){
now=vc[i];
}else{
_gcd(now,vc[i]);
if(now.F==0)swap(now,vc[i]);
s.push_back(vc[i].S);
}
}
}
ll sg=0;
int len=s.size();
for(int i=0;i<len;i++){
if(s[i]!=0){
if(sg==zo)sg=abs2(s[i]);
else sg=gcd(sg,abs2(s[i]));
}
}
if(now.F==0||sg==0){
cout<<"-1\n";
}else{
cout<<(long long)(now.F*sg)<<"\n";
}
return 0;
}