제출 #1038159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038159		holyhell	Portal (BOI24_portal)	C++17	100 / 100	48 ms	6232 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long x[301010],y[301010];
#define p64 pair<long long,long long>
long long f(p64 a, p64 b){return abs(a.first*b.second-a.second*b.first);}
long long gcd(long long a, long long b){return b?gcd(b,a%b):a;}
p64 gcd(p64 a, p64 b){return {gcd(a.first,b.first),gcd(a.second,b.second)};}
bool lin(p64 a, p64 b){return f(a,b)==0;}
p64 operator-(p64 a, p64 b){return {a.first-b.first,a.second-b.second};}
p64 operator*(p64 a, long long b){return {a.first*b,a.second*b};}
#define X 1000000007
long long exp_mod(long long a, long long b, long long m){
    long long out=1;
    for(;b;b>>=1){
        if(b&1)out=1ll*out*a%m;
        a=1ll*a*a%m;
    } return out;
}
pair<p64,p64> get(pair<p64,p64>a, p64 b){
    if(lin(a.first,a.second)){
        a.first=gcd(a.first,a.second);
        a.second=b;
        return a;
    }if(lin(a.first,b)){
        a.first=gcd(a.first,b);
        return a;
    }if(lin(a.second,b)){
        a.second=gcd(a.second,b);
        return a;
    } long long xx=a.first.first*a.second.second-a.first.second*a.second.first;
    long long aa=b.first*a.second.second-b.second*a.second.first; aa/=xx;
    long long bb=b.second*a.first.first-b.first*a.first.second; bb/=xx;
    p64 rem=b-a.first*aa-a.second*bb;
    return get({a.first,rem},a.second);
}
int main(){
    long long n; cin>>n;
    for(long long i=0;i<n;i++)cin>>x[i]>>y[i];
    for(long long i=0;i<n;i++) x[i]-=x[n-1],y[i]-=y[n-1];
    --n;
    pair<p64,p64>ans; ans.first={x[0],y[0]}; long long i;
    for(i=1;i<n;i++)if(!lin(ans.first,{x[i],y[i]})){
            ans.second={x[i],y[i]};
            break;
        } if(i==n){
        cout<<-1;return 0;

    }for(i=1;i<n;i++)ans=get(ans,{x[i],y[i]});
    long long out=f(ans.first,ans.second);
    if(out==0)cout<<-1;
    else cout<<out;
}

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