제출 #1012573

#제출 시각아이디문제언어결과실행 시간메모리
1012573ttamxPortal (BOI24_portal)C++17
21 / 100
20 ms2020 KiB
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=1e5+5;

int n;

struct Point{
    ll x,y;
    Point norm(){return x<0||(x==0&&y<0)?Point{-x,-y}:*this;}
    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-a.y*b.x;}

Point gcd(Point a,Point b){
    Point c;
    c.x=gcd(a.x,b.x);
    c.y=gcd(a.y,b.y);
    return c.norm();
}

pair<Point,Point> gcd2(Point u,Point v,Point q){
    if(cross(u,v)==0)return {gcd(u,v),q};
    if(cross(u,q)==0)return {gcd(u,q),v};
    if(cross(v,q)==0)return {gcd(v,q),u};
    ll d=cross(u,v);
    ll a=cross(q,v)/d;
    ll b=cross(u,q)/d;
    Point r=q-(u*a)-(v*b);
    assert(abs(cross(u,r))<abs(cross(u,v)));
    return gcd2(u,r,v);

}

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]).norm();
    bool ok=false;
    for(int i=3;i<=n;i++)if(cross(p[2],p[i])!=0){
        swap(p[3],p[i]);
        ok=true;
        break;
    }
    if(!ok)cout << -1,exit(0);
    Point u=p[2],v=p[3];
    for(int i=4;i<=n;i++)tie(u,v)=gcd2(u,v,p[i]);
    cout << abs(cross(u,v));
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...