Submission #997815

#	Time	Username	Problem	Language	Result	Execution time	Memory
997815		hengliao	Portal (BOI24_portal)	C++17	21 / 100	38 ms	6744 KiB

Main

#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

struct P{
    ll x, y;

    bool operator< (const P &tar) const{
        if(x!=tar.x){
            return x<tar.x;
        }
        return y<tar.y;
    }

    ll operator^ (const P &tar) const{
        return x*tar.y-y*tar.x;
    }

    P operator- (const P &tar) const{
        return {x-tar.x, y-tar.y};
    }

    P operator+ (const P &tar) const{
        return {x+tar.x, y+tar.y};
    }
};

void solve(){
	ll n;
    cin>>n;
    vector<P> p(n);
    for(auto &it:p){
        cin>>it.x>>it.y;
    }
    if(n==3){
        ll ans=(p[1]-p[0])^(p[2]-p[0]);
        if(ans==0){
            cout<<"-1\n";
            return;
        }
        cout<<abs(ans)<<'\n';
        return;
    }
    if(n==1){
        cout<<"-1\n";
        return;
    }
    sort(p.begin(), p.end());
    set<ll> st;
    for(auto &it:p){
        st.insert(it.x);
    }
    if(st.size()<=1){
        cout<<"-1\n";
        return;
    }
    ll gcd1=(*prev(st.end()))-(*st.begin());
    ll pre=(*st.begin());
    for(auto &it:st){
        //if(it==*st.begin()) continue;
        if(it-pre!=0) gcd1=__gcd(gcd1, it-pre);
        pre=it;
    }
    st.clear();
    for(auto &it:p){
        st.insert(it.y);
    }
    if(st.size()<=1){
        cout<<"-1\n";
        return;
    }
    ll gcd2=(*prev(st.end()))-(*st.begin());
    pre=(*st.begin());
    for(auto &it:st){
        //if(it==*st.begin()) continue;
        if(it-pre!=0) gcd2=__gcd(gcd2, it-pre);
        pre=it;
    }
    bool type1=1;
    pll comp={(p[1].x-p[0].x), (p[1].y-p[0].y)};
    //cout<<comp.F<<' '<<comp.S<<'\n';
    for(ll i=2;i<n;i++){
        ll f=(p[i].x-p[0].x);
        ll s=(p[i].y-p[0].y);
        if(f*comp.S!=s*comp.F){
            //cout<<f<<' '<<s<<'\n';
            type1=0;
            break;
        }
    }
    if(type1){
        cout<<"-1\n";
        return;
    }
    bool type2=1;
    for(ll i=1;i<n;i++){
        ll f=abs(p[i].x-p[0].x)/gcd1;
        ll s=abs(p[i].y-p[0].y)/gcd2;
        if((abs(f+s))%2!=0){
            type2=0;
            break;
        }
    }
    if(type2){
        cout<<gcd1*gcd2*2<<'\n';
        return;
    }
    cout<<gcd1*gcd2<<'\n';
    return;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	solve();
	return 0;
}

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