Submission #1165912

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

Main

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

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 cpr(pii p0, pii p1) {
    return labs(p0.first*p1.second-p0.second*p1.first);
}

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};
    for (ll i=1;i<N;i++) {
        ll x2,y2; cin >> x2 >> y2;
        v0.push_back({x2-x1,y2-y1});
    }
    vector<pii> vtest;
    vtest.push_back(v0[0]);
    for (ll i=1;i<(N-1);i++) {
        bool df = 0;
        for (pii p0: vtest) {
            ll ans1 = cpr(p0,v0[i]);
            if (gcd(ans,ans1)<ans) {
                df = 1;
            }
            ans = gcd(ans,ans1);
        }
        if (df) {
            vtest.push_back(v0[i]);
        }
    }
    if (ans==0) {
        cout << "-1\n";
    } else {
        cout << ans << "\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