제출 #1041453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041453		owoovo	Portal (BOI24_portal)	C++17	11 / 100	47 ms	5068 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define F first
#define S second

using namespace std;

pll fd(pll x){
    return max(x,{-x.F,-x.S});
}
pll base(pll x){
    if(x.F==0)return {0,1};
    else if(x.S==0)return {1,0};
    else {
        ll g=gcd(abs(x.F),abs(x.S));
        return {x.F/g,x.S/g};
    }
}
pll gg(pll x,pll y){
    if(x.F==0){
        return {0,gcd(abs(x.S),abs(y.S))};
    }else if(x.S==0){
        return {gcd(abs(x.F),abs(y.F)),0};
    }else{
        ll gf=gcd(abs(x.F),abs(y.F)),gs=gcd(abs(x.S),abs(y.S));
        return fd({gf,gs});
    }
}
bool build(pll x,pll y,pll tar){
    ll X=abs(y.F*tar.S-y.S*tar.F),Y=abs(x.F*tar.S-x.S*tar.F),D=abs(y.F*x.S-y.S*x.F);
    if(X%D==0&&Y%D==0)return 1;
    return 0;
}
int n;
vector<pll> point;
vector<pll> vc;
vector<pll> use;
int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        ll x,y;
        cin>>x>>y;
        point.push_back({x,y});
    }
    for(int i=1;i<n;i++){
        vc.push_back(fd({point[i].F-point[0].F,point[i].S-point[0].S}));
    }
    for(auto x:vc){
        assert(x.F>=0);
        int ok=1;
        for(auto y:use){
            if(base(x)==base(y)){
                y=gg(x,y);
                ok=0;
                break;
            }
        }
        if(ok==1){
            if(use.size()<2)use.push_back(x);
            else{
                if(build(use[0],x,use[1])){
                    use[1]=x;
                }else if(build(use[1],x,use[0])){
                    use[0]=x;
                }
            }
        }
        if(use.size()>=3){
            break;
        }
    }
    if(use.size()>=3){
        cout<<"1\n";
    }else if(use.size()<=1){
        cout<<"-1\n";
    }else{
        sort(use.begin(),use.end());
        if(use[0].F==0){
            cout<<abs(use[0].S*use[1].F)<<"\n";
        }else{
            ll g=gcd(abs(use[0].F),abs(use[1].F));
            ll diff=abs(use[0].S*use[1].F/g-use[1].S*use[0].F/g);
            cout<<g*diff<<"\n";
        }
    }
    return 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