Submission #1118796

#TimeUsernameProblemLanguageResultExecution timeMemory
1118796YSH2020Portal (BOI24_portal)C++17
40 / 100
69 ms6676 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans_x = 0;
int gcd(int a, int b) {
    if (a < 0) a *= -1;
    if (b < 0) b *= -1;
    if (b > a) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a%b);
}
 
pair<int, int> zero_vector (pair<int, int> a, pair<int, int> b) {
    if (a.first < 0) a = {-a.first, -a.second};
    if (b.first < 0) b = {-b.first, -b.second};
    if (b.first > a.first) swap(a, b);
    if (b.first == 0) {ans_x = gcd(ans_x, b.second); return a;}
    return zero_vector(b, {a.first%b.first, a.second-b.second*(a.first/b.first)});
}

signed main() {
    int n; cin >> n;
    if (n < 3) {cout << -1; return 0;}
    int x[n], y[n];
    for (int i = 0; i < n; i++) {cin >> x[i] >> y[i];}
    vector <pair<int, int>> a;
    for (int i = 1; i < n; i++) {
        if (x[i] == x[i-1]) {
            ans_x = gcd(ans_x, y[i]-y[i-1]);
        }
        else if (x[i] > x[i-1]) {
            a.push_back({x[i]-x[i-1], y[i]-y[i-1]});
        }
        else a.push_back({x[i-1]-x[i], y[i-1]-y[i]});
    }
    while (a.size() >= 2) {
        auto i = a.back();
        a.pop_back();
        a[0] = zero_vector(a[0], i);
    }
    if (a.size() == 0 or a[0].first == 0 or ans_x == 0) cout << -1;
    else cout << a[0].first*ans_x;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...