| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1049466 | shenfe1 | 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>
#pragma optimize("Ofast")
#pragma target("avx2")
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define in insert
#define int ll
const int MAX=3e5+15;
const ll inf=1e18+1;
const int mod=998244353;
const int mod1=1e9+9;
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
int binpow(int a,int n){
if(!n)return 1;
if(n%2==1)return a*binpow(a,n-1)%mod;
int k=binpow(a,n/2);
return k*k%mod;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
pair<pair<int,__int128>,pair<int,__int128>> gcd(pair<int,__int128> a,pair<int,__int128> b){
if(a.F==0||b.F==0)return {a,b};
if(a.F<b.F)swap(a,b);
int c=a.F/b.F;
a.F%=b.F;
a.S-=b.S*c;
return gcd(b,a);
}
int x[MAX],y[MAX];
void solve(){
cin>>n;
if(n<=2){
cout<<-1<<"\n";
return;
}
for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
__int128 g=0;
set<pair<int,__int128>> vec;
for(int i=2;i<=n;i++){
if(x[i]==x[1]){
if(y[i]!=y[1]){
__int128 f=y[i]-y[1];
g=gcd(g,f);
}
}
else{
if(x[i]-x[1]>0)vec.insert({x[i]-x[1],y[i]-y[1]});
else vec.insert({x[1]-x[i],y[1]-y[i]});
}
}
while(sz(vec)>=2){
// cerr<<sz(vec)<<" "<<vec[0].F<<" "<<vec[0].S<<" "<<vec[1].F<<" "<<vec[1].S<<"\n";
pair<int,__int128> a=*vec.begin();
vec.erase(vec.begin());
pair<int,__int128> b=*vec.begin();
vec.erase(vec.begin());
pair<pair<int,__int128>,pair<int,__int128>> res=gcd(a,b);
// if(res.F==make_pair(0ll,0ll))cout<<"1WTF\n";
// if(res.S==make_pair(0ll,0ll))cout<<"WTF\n";
// cout<<res.F.F<<" "<<res.F.S<<" "<<res.S.F<<" "<<res.S.S<<"\n";
if(res.F.F==0){
if(res.F.S!=0){
g=gcd(g,res.F.S);
}
}
else vec.insert(res.F);
if(res.S.F==0){
if(res.S.S!=0){
g=gcd(g,res.S.S);
}
}
else vec.insert(res.S);
}
if(vec.empty()||g==0)cout<<-1<<"\n";
else{
// cout<<g<<" "<<vec.begin()->F<<" "<<vec.begin()->S<<"\n";
int G=g;
cout<<G*vec.begin()->F<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
}