이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
tuple<ll, ll, ll> euclid(ll a, ll b){
if(b == 0) return {a, 1, 0};
ll q = a/b;
auto [g, s, t] = euclid(b, a - q*b);
return {g, t, s - q*t};
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int n;
cin >> n;
vector<ll> x(n), y(n);
for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
if(n <= 2){
cout << "-1\n";
return 0;
}
vector<vector<ll>> a(2, vector<ll>(n-1));
for(int i = 0; i < n-1; i++){
a[0][i] = x[i+1] - x[0];
a[1][i] = y[i+1] - y[0];
}
for(int i = 0; i < n-1; i++){
if(a[0][i] != 0){
swap(a[0][0], a[0][i]);
swap(a[1][0], a[1][i]);
break;
}
}
if(a[0][0] == 0){
cout << "-1\n";
return 0;
}
for(int i = 1; i < n-1; i++){
auto [g, s, t] = euclid(a[0][0], a[0][i]);
ll a00 = a[0][0] * s + a[0][i] * t;
ll a10 = a[1][0] * s + a[1][i] * t;
ll a0i = 0;
ll a1i = a[1][0] * (-a[0][i]/g) + a[1][i] * (a[0][0] / g);
a[0][0] = a00;
a[1][0] = a10;
a[0][i] = a0i;
a[1][i] = a1i;
}
ll g = 0;
for(int i = 1; i < n-1; i++){
g = gcd(g, a[1][i]);
}
if(g == 0) cout << "-1\n";
else cout << abs(g * a[0][0]) << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |