Submission #1118796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118796		YSH2020	Portal (BOI24_portal)	C++17	40 / 100	69 ms	6676 KiB

Main

#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;
}

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