Submission #1356105

#TimeUsernameProblemLanguageResultExecution timeMemory
1356105AvianshPortal (BOI24_portal)C++20
1 / 100
13 ms1992 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

int cross(array<int,2>a, array<int,2>b){
    return (a[0]*b[1]-b[0]*a[1]);
}

pair<int,int> euclid(int a, int b){
    if(b==0){
        return {1,0};
    }
    pair<int,int>ans = euclid(b,a%b);
    swap(ans.first,ans.second);
    ans.second-=(a/b)*ans.first;
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    array<int,2>pts[n];
    for(int i = 0;i<n;i++){
        cin >> pts[i][0];
        cin >> pts[i][1];
    }
    if(n<=2){
        cout << -1;
        return 0;
    }
    for(int i = n-1;i>=0;i--){
        pts[i][0]-=pts[0][0];
        pts[i][1]-=pts[0][1];
    }
    array<int,2>pt1 = pts[1];
    array<int,2>pt2 = {0,0};
    for(int i = 2;i<n;i++){
        if(cross(pt1,pts[i])){
            pt2=pts[i];
            break;
        }
    }
    if(pt2==(array<int,2>){0,0}){
        cout << -1;
        return 0;
    }
    int y = gcd(pt1[1],pt2[1]);
    int d = abs(cross(pt1,pt2))/y;
    pair<int,int>p = euclid(pt1[1],pt2[1]);
    int x = p.first*pt1[0]+p.second*pt2[0];
    x%=d;
    for(int i = 1;i<n;i++){
        if(pts[i][1]==0){
            ///only x coord
            d=gcd(d,pts[i][0]);
        }
        else{
            ///potentially both
            d=gcd(d,(pts[i][1]*x-y*pts[i][0])/gcd(y,pts[i][1]));
            d=abs(d);
            p=euclid(y,pts[i][1]);
            x=x*p.first+pts[i][1]*p.second;
            y=gcd(y,pts[i][1]);
        }
        x%=d;
    }
    cout << abs(d*y);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...