Submission #1041446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041446		owoovo	Portal (BOI24_portal)	C++17	11 / 100	2096 ms	4944 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&&(use.size()!=2||build(use[0],use[1],x)==0)){
            use.push_back(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