제출 #1219575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219575		12345678	Portal (BOI24_portal)	C++20	11 / 100	2097 ms	4088 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

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
        {
            auto mn=min({abs(cross(a, b)), abs(cross(a, c)), abs(cross(b, c))});
            if (cross(a, b)==mn)
            {
                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;
            }
            else if (cross(a, c)==mn)
            {
                swap(b, c);
                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;
            }
            else
            {
                swap(a, c);
                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: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35