Submission #1125690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125690		tte0	Portal (BOI24_portal)	C++20	1 / 100	2094 ms	2488 KiB

Main

// Author: Teoman Ata Korkmaz
#include <bits/stdc++.h> 
#define int int_fast64_t
using namespace std;
///////////////////////////////////////////////////////////
int n,mnx,mny;
vector<tuple<int,int>> v;

signed main(void){
    cin>>n;
    int x,y,a,b;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        if(!i)a=x,b=y;
        v.push_back({x-a,y-b});
    }

    // for(auto [a,b]:v){
    //     cerr<<"v:"<<a<<","<<b<<endl;
    // }

    int ansx=0,ansy=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            // cerr<<"i,j:"<<i<<" "<<j<<endl;
            auto [xi,yi]=v[i];
            auto [xj,yj]=v[j];
            if(xi<0)xi*=-1,yi*=-1;
            if(xj<0)xj*=-1,yj*=-1;
            
            int a=(xi==xj) ? yi : yi*(xj/gcd(xi,xj));
            int b=(xi==xj) ? yj : yj*(xi/gcd(xi,xj));

            // cerr<<"a";
            // cerr<<"ax,bx:"<<a<<","<<b<<endl;

            ansx=gcd(ansx,abs(a-b));
            // cerr<<"a";
            if(yi<0)xi*=-1,yi*=-1;
            if(yj<0)xj*=-1,yj*=-1;
            // cerr<<"a";

            a=(yi==yj) ? xi : xi*(yj/gcd(yi,yj));
            b=(yi==yj) ? xj : xj*(yi/gcd(yi,yj));

            // cerr<<"a";
            // cerr<<"ay,by:"<<a<<","<<b<<endl;

            ansy=gcd(ansy,abs(a-b));
            // cerr<<"a"<<endl;
        }
    }

    // cerr<<"ansx,ansy:"<<ansx<<","<<ansy<<endl;
    cout<<(ansx && ansy ? (ansx/gcd(ansx,ansy))*ansy : -1)<<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