| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1041523 | owoovo | Portal (BOI24_portal) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define F first
#define S second
using namespace std;
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(){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// 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);
if(diff==0){
ll G=gcd(abs(use[j].F),abs(use[i].F));
diff=abs(use[1].S*use[0].F/G-use[0].S*use[1].F/G);
}
for(int t=0;t<20000000;t++){
int i=distrib(rng),j=distrib(rng);
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;
}