Submission #1045426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045426		Darren0724	Portal (BOI24_portal)	C++17	11 / 100	2096 ms	3420 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define rz resize
#define pb emplace_back
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int INF=9e18;
const int mod=1e9+7;
const int N=200005;
const int K=20;
const int C=2000005;

int gcd(int a,int b){
    return abs(__gcd(a,b));
}

 
int32_t main(){
    LCBorz;
    int n;cin>>n;
    if(n<=2){
        cout<<-1<<endl;
        return 0;
    }
    vector<pair<int,int>> v(n),v1(n);
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        v[i]={a,b};
    }
    sort(all(v));
    for(int i=1;i<n;i++){
        v[i].x-=v[0].x;
        v[i].y-=v[0].y;
    }
    int ans=-1;
    if(v[1].y==0&&v[2].y==0){
        cout<<-1<<endl;
        return 0;
    }
    if(v[1].y==0){
        cout<<abs(v[1].x*v[2].y)<<endl;
        return 0;
    }
    if(v[2].y==0){
        cout<<abs(v[2].x*v[1].y)<<endl;
        return 0;
    }
    //cout<<v[1].x<<' '<<v[1].y<<' '<<v[2].x<<' '<<v[2].y<<endl;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(v[i].y==0&&v[j].y==0){
                continue;
            }
            if(v[i].y==0){
                ans=(ans==-1?v[i].x:gcd(v[i].x,ans));
                continue;
            }
            if(v[j].y==0){
                ans=(ans==-1?v[j].x:gcd(v[j].x,ans));
                continue;
            }
            int r1=v[j].y/gcd(v[i].y,v[j].y);
            int t=v[i].y*r1;
            int t1=t/v[j].y;
            int x1=abs(v[i].x*r1-v[j].x*t1);
            //cout<<r1<<' '<<t1<<endl;
            //cout<<x1<<endl;
            if(x1!=0)ans=(ans==-1?x1:gcd(ans,x1));
        }
    }
    int g1=gcd(v[1].y,v[2].y);
    /*for(int i=1;i<n;i++){
        if(v[i].y==0)continue;
        g1=(g1==-1?abs(v[i].y):gcd(g1,v[i].y));
    }*/
    //cout<<ans<<' '<<g1<<endl;
    cout<<(ans==-1?-1:ans*g1)<<endl;
    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