Submission #1331391

#TimeUsernameProblemLanguageResultExecution timeMemory
1331391AndreyPortal (BOI24_portal)C++20
100 / 100
17 ms2628 KiB
#include<bits/stdc++.h>
using namespace std;

long long d,x,y;

long long gcd(long long a, long long b) {
    a = abs(a);
    b = abs(b);
    if(b == 0) {
        return a;
    }
    return gcd(b,a%b);
}

pair<long long,long long> euclid(long long a, long long b) {
    if(b == 0) {
        return {1,0};
    }
    pair<long long,long long> ans;
    if(abs(a) < abs(b)) {
        ans = euclid(b,a);
        return {ans.second,ans.first};
    }
    else {
        long long c = abs(a)/abs(b);
        if(a*b < 0) {
            c = -c;
        }
        ans = euclid(a-c*b,b);
        return {ans.first,ans.second-c*ans.first};
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n;
    cin >> n;
    if(n <= 2) {
        cout << -1;
        return 0;
    }
    long long x0,y0,a,b;
    cin >> x0 >> y0;
    vector<pair<long long,long long>> haha(0);
    for(long long i = 1; i < n; i++) {
        cin >> a >> b;
        a-=x0;
        b-=y0;
        haha.push_back({a,b});
    }
    pair<long long,long long> p1 = haha[0],p2 = {0,0};
    for(long long i = 1; i < n-1; i++) {
        if(p1.first*haha[i].second != p1.second*haha[i].first) {
            p2 = haha[i];
        }
    }
    if(p2.first == 0 && p2.second == 0) {
        cout << -1;
        return 0;
    }
    long long e = gcd(p1.second,p2.second);
    d = (p1.first*p2.second-p2.first*p1.second)/e;
    d = abs(d);
    pair<long long,long long> q = euclid(p1.second,p2.second);
    x = q.first*p1.first+q.second*p2.first;
    x = x%d;
    y = q.first*p1.second+q.second*p2.second;
    for(long long i = 1; i < n-1; i++) {
        pair<long long,long long> p = haha[i];
        long long e = gcd(p.second,y);
        if(p.second == 0) {
            d = gcd(d,p.first);
        }
        else {
            d = gcd(d,(x*p.second-y*p.first)/e);
            pair<long long,long long> q = euclid(y,p.second);
            x = x*q.first+p.first*q.second;
            y = q.first*y+q.second*p.second;
        }
        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...