Submission #1264788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264788		Nika533	Portal (BOI24_portal)	C++20	1 / 100	2094 ms	3260 KiB

Main

#include <bits/stdc++.h>
// #define int long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
using namespace std;

const int N=1e5+5,A=1e6+5;
int n,x[N],y[N];

int s[A],p[A];
void make_set(int v) {
    p[v]=v; s[v]=1;
}
int find_set(int v) {
    if (p[v]==v) return v;
    return p[v]=find_set(p[v]);
}
void merge_set(int a, int b) {
    a=find_set(a); b=find_set(b);
    if (a==b) return;
    if (s[a]<s[b]) swap(a,b);
    s[a]+=s[b]; p[b]=a;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    vector<pii> v;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i];
    vector<int> xx,yy;
    for (int i=1; i<=n; i++) {
        v.pb({x[i],y[i]});
        xx.pb(x[i]); yy.pb(y[i]);
    }
    sort(all(v)); sort(all(xx)); sort(all(yy));
    bool check=true;
    int X=0,Y=0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            X=__gcd(X,abs(x[i]-x[j]));
            Y=__gcd(Y,abs(y[i]-y[j]));
        }
    }
    if (X!=0 && Y!=0) {
        for (int i=2; i<n; i++) {
            if ((v[1].f-v[0].f)*(v[i].s-v[i-1].s)!=(v[1].s-v[0].s)*(v[i].f-v[i-1].f)) check=false;
        }
    }
    if (xx[0]==xx[n-1] || yy[0]==yy[n-1]) check=true;
    if (check) {
        cout<<-1<<endl;
        return 0;
    }
    cout<<X*Y<<endl;
    return 0;
    // sort(x+1,x+1+n); sort(y+1,y+1+n);
    int num=200;
    for (int i=0; i<=num; i++) {
        for (int j=0; j<=num; j++) {
            make_set(i+j*(num+1));
        }
    }
    for (int i=0; i<=num; i++) {
        for (int j=0; j<=num; j++) {
            int num1=i+j*(num+1);
            // for (int ii=1; ii<=n; ii++) {
            //     int jj=1;
            //     int i1=i+x[ii]-x[jj];
            //     int j1=j+y[ii]-y[jj];
            //     int num2=i1+j1*(num+1);
            //     if (0<=i1 && i1<=num && 0<=j1 && j1<=num) {
            //         merge_set(num1,num2);
            //     }
            // }
            for (int ii=1; ii<=n; ii++) {
                for (int jj=1; jj<=n; jj++) {
                    int i1=i+x[ii]-x[jj];
                    int j1=j+y[ii]-y[jj];
                    int num2=i1+j1*(num+1);
                    if (0<=i1 && i1<=num && 0<=j1 && j1<=num) {
                        merge_set(num1,num2);
                    }
                }
            }
        }
    }
    set<int> myset;
    for (int i=0; i<=num; i++) {
        for (int j=0; j<=num; j++) {
            myset.insert(find_set(i+j*(num+1)));
        }
    }
    cout<<myset.size()<<endl;
}

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