Submission #1098497

#TimeUsernameProblemLanguageResultExecution timeMemory
1098497_8_8_Portal (BOI24_portal)C++17
100 / 100
21 ms7120 KiB
#include <bits/stdc++.h>
    
using namespace std;
    
// typedef long long ll;
const int  N = 3e5 + 12, MOD = (int)1e9 + 7;
    
using ll = __int128_t;
int n, x[N], y[N];
ll G = 0;
vector<array<ll, 2>> a;
    
__int128 gcd(__int128 a,__int128 b){
    // cr(a),cr(b);
    if(b<0)b*=-1;
    if(a<0)a*=-1;
    if(a==0)return b;
    if(b==0)return a;
    if(a<b)swap(a,b);
    return gcd(b,a%b);
}
array<ll, 2> Gcd(array<ll, 2> c,array<ll, 2> d) {
    if(!c[0]) {
        G = gcd(G, c[1]);
        return d;
    }
    if(!d[0]) {
        G = gcd(G, d[1]);
        return c;
    }
    if(c[0] < d[0]) {
        swap(c, d);
    }
    ll col = c[0] / d[0];
    c[0] -= col * 1ll * d[0];
    c[1] -= col * 1ll * d[1];
    return Gcd(c, d);
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    for(int i = 2; i <= n; i++) {
        if(x[i] == x[i - 1]) {
            ll v = y[i] - y[i - 1];
            if(v < 0) v = -v;
            G = gcd(G, v);
            continue;
        }
        if(x[i] > x[i - 1]) {
            a.push_back({x[i] - x[i - 1], y[i] - y[i - 1]});
        } else {
            a.push_back({x[i - 1] - x[i], y[i - 1] - y[i]});
        }
    }
    while((int)a.size() >= 2) {
        auto i = a.back();
        a.pop_back();
        auto k = Gcd(i, a[0]);
        a[0] = k;
    }
    if(a.empty() || !a[0][0]|| !G) {
        cout << -1 << '\n';
        return;
    }
    long long res = G * a[0][0];
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    
    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...