Submission #1219577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219577		12345678	Portal (BOI24_portal)	C++20	100 / 100	39 ms	4032 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

mt19937 rng(time(0));

const int nx=1e5+5;

ll n, x[nx], y[nx];

struct myvector
{
    ll x, y;
    myvector(ll x=0, ll y=0): x(x), y(y){}
    bool operator< (const myvector &o) const {return 1;}
};
vector<myvector> v;

ll cross(myvector a, myvector b)
{
    return a.x*b.y-a.y*b.x;
}

myvector merge(myvector a, myvector b)
{
    return myvector(__gcd(a.x, b.x), __gcd(a.y, b.y));
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i];
    for (int i=2; i<=n; i++) v.push_back(myvector(x[i]-x[1], y[i]-y[1]));
    while (v.size()>=3)
    {
        auto a=v.back();
        v.pop_back();
        auto b=v.back();
        v.pop_back();
        auto c=v.back();
        v.pop_back();
        if (cross(a, b)==0) v.push_back(merge(a, b)), v.push_back(c);
        else if (cross(b, c)==0) v.push_back(merge(b, c)), v.push_back(a);
        else if (cross(a, c)==0) v.push_back(merge(a, c)), v.push_back(b);
        else
        {
            vector<pair<ll, myvector>> tmp={{rng(), a}, {rng(), b}, {rng(), c}};
            sort(tmp.begin(), tmp.end());
            a=tmp[0].second;
            b=tmp[1].second;
            c=tmp[2].second;
            ll k=(b.y*c.x-b.x*c.y)/(b.y*a.x-b.x*a.y);
            ll l=(a.y*c.x-a.x*c.y)/(a.y*b.x-a.x*b.y);
            c.x-=k*a.x+l*b.x;
            c.y-=k*a.y+l*b.y;
            v.push_back(a);
            v.push_back(b);
            v.push_back(c);
        }
    }
    if (v.size()<=1||(v.size()==2&&cross(v[0], v[1])==0)) cout<<-1;
    else cout<<abs(cross(v[0], v[1]));
}

/*
3
1 2
4 1
0 0

*/

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