Submission #1165909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165909		Math4Life2020	Portal (BOI24_portal)	C++20	11 / 100	21 ms	2496 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;

ll gcd2(ll a, ll b) {
    a = labs(a); b = labs(b);
    if (a==0) {
        return b;
    }
    if (b==0) {
        return a;
    }
    return gcd(a,b);
}

ll inv(ll x, ll MOD) {
    if (MOD<0) {
        MOD = -MOD;
    }
    x = (x+MOD*(2-x/MOD))%MOD;
    array<ll,3> a = {x,1,0};
    array<ll,3> b = {MOD,0,1};
    while (b[0]!=1) {
        if (a[0]>b[0]) {
            swap(a,b);
        } else {
            ll k = b[0]/a[0];
            for (ll i=0;i<3;i++) {
                b[i]-=k*a[i];
            }
        }
    }
    ll vf = b[1];
    vf = (vf+MOD*(2-vf/MOD))%MOD;
    return vf;
}

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

pii RFZ(pii p1, pii p2) {
    if (p1.first<0 ^ p2.first<0) {
        p1.first=-p1.first; p1.second=-p1.second;
    }
    return {sgn(p1.first)*gcd2(p1.first,p2.first),sgn(p1.second)*gcd2(p1.second,p2.second)};
}

pair<pii,pii> fz(pair<pii,pii> A0, pii pt) {
    pii p0 = A0.first; pii p1 = A0.second;
    if (A0.second.first==-INF) {
        if (p0.first*pt.second!=p0.second*pt.first) {
            return {p0,pt};
        } else {
            return A0;
        }
    }
    ll G = labs(p0.first*p1.second-p0.second*p1.first);
    ll G0 = labs(p0.first*pt.second-p0.second*pt.first);
    ll G1 = labs(p1.first*pt.second-p1.second*pt.first);
    if (G0%G==0 && G1%G==0) {
        return A0;
    }
    //else we can get a better gcd!
    ll L1 = p0.first*p1.second-p0.second*p1.first;
    ll L2 = p0.first*pt.second-p0.second*pt.first;
    //cout << "pt="<<pt.first<<","<<pt.second<<"\n";
    assert(L1!=0);
    if (L2==0) {
        return {p1,RFZ(p0,pt)};
    }
    ll LG = gcd2(L1,L2);
    L1 = L1/LG; L2 = L2/LG;
    ll A = inv(L1,L2);
    //cout << "L1,L2="<<L1<<","<<L2<<"\n";
    //cout << "A="<<A<<"\n";
    ll B = (1-A*L1)/L2;
    pii pfn = {A*p1.first+B*pt.first,A*p1.second+B*pt.second};
    //cout << "f2\n";
    return {p0,pfn};
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
	ll N; cin >> N;
    ll ans = 0;
    if (N<=2) {
        cout << "-1\n"; exit(0);
    }
    vector<pii> v0;
    pii p0;
    ll x1,y1; cin >> x1 >> y1;
    p0 = {x1,y1};
    ll g1t = 0; ll g2t = 0;
    for (ll i=1;i<N;i++) {
        ll x2,y2; cin >> x2 >> y2;
        v0.push_back({x2-x1,y2-y1});
        g1t = gcd2(g1t,x2-x1);
        g2t = gcd2(g2t,y2-y1);
    }
    if (g1t == 0 || g2t == 0) {
        cout << "-1\n"; exit(0);
    }
    pair<pii,pii> mem;
    mem = {v0[0],{-INF,-INF}};
    for (ll i=1;i<(N-1);i++) {
        mem = fz(mem,v0[i]);
        //cout << "mem: "<<mem.first.first<<","<<mem.first.second<<"; "<<mem.second.first<<","<<mem.second.second<<"\n";
    }
    if (mem.second.first==-INF) {
        cout << "-1\n"; exit(0);
    } else {
        cout << labs(mem.first.first*mem.second.second-mem.first.second*mem.second.first) << "\n";
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35