제출 #1369605

#제출 시각아이디문제언어결과실행 시간메모리
1369605Charizard2021Portal (BOI24_portal)C++20
100 / 100
13 ms1860 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128_t;

i128 abs128(i128 x){
    return x < 0 ? -x : x;
}

i128 gcd128(i128 a, i128 b){
    a = abs128(a);
    b = abs128(b);

    while(b != 0){
        i128 r = a % b;
        a = b;
        b = r;
    }

    return a;
}

ll egcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }

    ll x1, y1;
    ll g = egcd(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return g;
}

void print128(i128 x){
    if(x == 0){
        cout << 0;
        return;
    }

    if(x < 0){
        cout << '-';
        x = -x;
    }

    string s;
    while(x > 0){
        s.push_back('0' + x % 10);
        x /= 10;
    }

    reverse(s.begin(), s.end());
    cout << s;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<ll> x(N), y(N);
    for(int i = 0; i < N; i++){
        cin >> x[i] >> y[i];
    }

    ll bx = x[0];
    ll by = y[0];

    ll p = 0;
    i128 t = 0;
    i128 h = 0;

    for(int i = 1; i < N; i++){
        ll X = x[i] - bx;
        ll Y = y[i] - by;

        if(X == 0){
            h = gcd128(h, (i128)Y);

            if(p > 0 && h > 0){
                t %= h;
                if(t < 0) t += h;
            }

            continue;
        }

        if(p == 0){
            if(X < 0){
                p = -X;
                t = -(i128)Y;
            }
            else{
                p = X;
                t = Y;
            }

            if(h > 0){
                t %= h;
                if(t < 0) t += h;
            }

            continue;
        }

        ll ax = llabs(X);
        ll newp = gcd(p, ax);

        ll A, B;
        egcd(p, ax, A, B);

        if(X < 0) B = -B;

        i128 vertical =
            ((i128)X / newp) * t - ((i128)p / newp) * Y;

        h = gcd128(h, vertical);

        i128 newt = (i128)A * t + (i128)B * Y;

        p = newp;
        t = newt;

        if(h > 0){
            t %= h;
            if(t < 0) t += h;
        }
    }

    if(p > 0 && h > 0){
        print128((i128)p * h);
        cout << '\n';
    }
    else{
        cout << -1 << '\n';
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…