Submission #1339914

#TimeUsernameProblemLanguageResultExecution timeMemory
1339914ZicrusPortal (BOI24_portal)C++20
40 / 100
32 ms1860 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
constexpr ll inf = 4e18;
mt19937 mt(time(0));

typedef complex<ll> point;
#define X real()
#define Y imag()

ll cross(point a, point b) {
    return a.X * b.Y - a.Y * b.X;
}

ll sgn(ll x) { return (x > 0) - (x < 0); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b == 0) return x = sgn(a), y = 0, abs(a);
    ll g = euclid(b, a % b, y, x);
    return y -= x * (a / b), g;
}

#define pmod(a,m) (((a)%(m)+(m))%(m))

pll mod_div(ll a, ll b, ll m) {
    m = abs(m); a = pmod(a,m); b = pmod(b,m);
    ll g = gcd(b,m); m/=g; if (a%g) return pll(-1, -1);
    ll x,y; euclid(b/g, m, x, y);
    return pll(pmod(a/g*x, m), m);
}

pll mod_isect(pll a, pll b, ll m) {
    if (min(a, b) == pll(-1, -1)) return pll(-1, -1);
    return mod_div(b.first - a.first, a.second - b.second, m);
}

void solve() {
    ll n; cin >> n;
    if (n <= 2) return cout << "-1\n", void();
    vector<point> pts(n - 1);
    ll ox, oy; cin >> ox >> oy;
    for (auto &p : pts) {
        ll x, y; cin >> x >> y;
        p = point(x - ox, y - oy);
    }
    ll e0g = gcd(pts[0].X, pts[0].Y);
    point e0 = pts[0] / e0g;
    point e1; {
        ll x, y;
        assert(euclid(e0.X, e0.Y, x, y) == 1);
        e1 = point(-y, x);
    }
    assert(cross(e0, e1) == 1);

    ll cg = 0;
    for (auto &p : pts) cg = gcd(cg, cross(e0, p));
    e1 *= cg; if (!cg) return cout << "-1\n", void();
    for (ll d = e0g; d >= 1; d--) {
        if (e0g % d) continue;
        pll line = pll(0, 1);
        for (auto &p : pts) {
            ll c = cross(e0, p) / cg;
            point v = e1 * c;
            ll k = real((p - v) / e0);
            line = mod_isect(line, mod_div(k, c, d), d);
        }
        if (line == pll(-1, -1)) continue;
        cout << d * cg << '\n';
        return;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    solve();
}
#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...