Submission #1041495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041495		owoovo	Portal (BOI24_portal)	C++17	65 / 100	113 ms	8524 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define F first
#define S second

using namespace std;
std::default_random_engine generator( time(NULL) );

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}));
    }
    int line=1;
    for(int i=1;i<vc.size();i++){
        if(base(vc[0])!=base(vc[i])){
            line=0;
            break;
        }
    }
    if(line==1){
        cout<<"-1\n";
    }else{
        ll g=0,diff=0;
        for(auto x:vc){
            if(x.F==0){
                if(diff==0)diff=abs(x.S);
                else diff=gcd(diff,abs(x.S));
                continue;
            }
            use.push_back(x);
            if(g==0)g=abs(x.F);
            else g=gcd(g,abs(x.F));
        }
        std::uniform_int_distribution<> distrib(0, use.size()-1);
        for(int t=0;t<1000000;t++){
            int i=distrib(generator),j=distrib(generator);
            if(i==j)continue;
            ll G=gcd(abs(use[j].F),abs(use[i].F));
            diff=gcd(diff,abs(use[j].S*use[i].F/G-use[i].S*use[j].F/G));
        }
        cout<<g*diff<<"\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=1;i<vc.size();i++){
      |                 ~^~~~~~~~~~

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