제출 #1165951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165951		Math4Life2020	Portal (BOI24_portal)	C++20	11 / 100	12 ms	2580 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) {
    if (a==0) {
        return b;
    }
    if (b==0) {
        return a;
    }
    return gcd(labs(a),labs(b));
}

ll cpr(pii p1, pii p2) {
    return (p1.first*p2.second-p1.second*p2.first);
}

pii fix(pii p1, pii p2) { //assuming cpr = 0, adjust both
    if (p1.first==0 && p1.second==0) {
        return p2;
    }
    if (p2.first==0 && p2.second==0) {
        return p1;
    }
    if (p1.first==0 && p2.first==0) {
        return {0LL,gcd2(p1.second,p2.second)};
    }
    if (p1.second==0 && p2.second==0) {
        return {gcd2(p1.first,p2.first),0LL};
    }
    ll a = gcd2(p1.first,p2.first);
    return {a,(p1.second*a)/p1.first};
}

pair<pii,pii> tw(pair<pii,pii> A0) {
    return {A0.second,A0.first};
}

ll inv(ll x, ll MOD) {
    assert(MOD>0);
    array<ll,3> a = {(x+MOD*(2-x/MOD))%MOD,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 fv = b[1];
    return (fv+MOD*(2-fv/MOD))%MOD;
}

pair<pii,pii> fz(pair<pii,pii> A0, pii pf) {
    pii p0 = A0.first; pii p1 = A0.second;
    //cout << "input: p0/p1= "<<p0.first<<","<<p0.second<<"; "<<p1.first<<","<<p1.second<<"\n";
    //cout << "input: pf= "<<pf.first<<","<<pf.second<<"\n";
    ll L0 = cpr(p0,p1);
    ll L1 = cpr(p0,pf);
    if (L1==0) {
        //cout << "fix: "<<fix(p0,pf).first<<","<<fix(p0,pf).second<<"\n";
        return {fix(p0,pf),p1};
    }
    if (gcd2(L0,L1)==labs(L0)) {
        return A0;
    }
    ll LG = gcd2(L0,L1);
    L0 = L0/LG; L1 = L1/LG;
    if (L1<0) {
        L0 = -L0; L1 = -L1;
    }
    //cout << "L0,L1="<<L0<<","<<L1<<"\n";
    ll A = inv(L0,L1);
    ll B = (1-A*L0)/L1;
    //cout << "A,B="<<A<<","<<B<<"\n";
    assert((1-A*L0)%L1==0);
    pii PEND = {p1.first*A+pf.first*B,p1.second*A+pf.second*B};
    //cout << "new after p0: "<<PEND.first<<","<<PEND.second<<"\n";
    return {p0,PEND};
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N; cin >> N;
    if (N<=2) {
        cout << "-1\n"; exit(0);
    }
    ll x1,y1; cin >> x1 >> y1;
    vector<pii> v0;
    for (ll i=0;i<(N-1);i++) {
        ll x2,y2; cin >> x2 >> y2;
        v0.push_back({x2-x1,y2-y1});
    }
    pii pa = v0[0]; pii pb = {-INF,-INF};
    bool tkb = false;
    for (ll i=1;i<(N-1);i++) {
        pii pc = v0[i];
        if (!tkb) {
            if (cpr(pa,pc)==0) {
                pa = fix(pa,pc);
            } else {
                tkb = 1; pb = pc;
            }
        } else {
            if (cpr(pa,pc)==0) {
                pa = fix(pa,pc);
            } else if (cpr(pb,pc)==0) {
                pb = fix(pb,pc);
            } else {
                pair<pii,pii> MEM = {pa,pb};
                while(1) {
                    ll ans0 = labs(cpr(MEM.first,MEM.second));
                    MEM = fz(MEM,pa);
                    MEM = tw(MEM);
                    MEM = fz(MEM,pa);
                    MEM = fz(MEM,pb);
                    MEM = tw(MEM);
                    MEM = fz(MEM,pb);
                    MEM = fz(MEM,pc);
                    MEM = tw(MEM);
                    MEM = fz(MEM,pc);
                    ll ans1 = labs(cpr(MEM.first,MEM.second));
                    assert(ans1<=ans0);
                    assert(ans0%ans1==0);
                    if (ans1==ans0) {
                        break;
                    } 
                }
                pa = MEM.first; pb = MEM.second;
            }
        }
    }
    if (!tkb) {
        cout << "-1\n"; exit(0);
    }
    cout << labs(cpr(pa,pb)) <<"\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