Submission #1012594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012594		ttamx	Portal (BOI24_portal)	C++17	100 / 100	25 ms	3460 KiB

Main

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=1e5+5;

int n;

struct Point{
    ll x,y;
    Point operator+(const Point &p)const{return {x+p.x,y+p.y};}
    Point operator-(const Point &p)const{return {x-p.x,y-p.y};}
    Point operator*(ll k)const{return {x*k,y*k};}
}p[N];

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

Point gcd(Point a,Point b){
    ll d=a.x?a.x/gcd(a.x,b.x):a.y/gcd(a.y,b.y);
    return {a.x/d,a.y/d};
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++)cin >> p[i].x >> p[i].y;
    for(int i=2;i<=n;i++)p[i]=p[i]-p[1];
    bool ok=false;
    for(int i=3;i<=n;i++)if(cross(p[2],p[i])!=0)ok=true;
    if(!ok)cout << -1,exit(0);
    Point u=p[2],v=p[3];
    for(int i=4;i<=n;i++){
        Point q=p[i];
        while(true){
            if(cross(u,v)==0){
                u=gcd(u,v),v=q;
                break;
            }
            if(cross(u,q)==0){
                u=gcd(u,q);
                break;
            }
            if(cross(v,q)==0){
                v=gcd(v,q);
                break;
            }
            ll d=cross(u,v);
            ll a=cross(q,v)/d;
            ll b=cross(u,q)/d;
            q=q-u*a-v*b;
            swap(v,q);
        }
    }
    cout << abs(cross(u,v));
}

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