Submission #1310024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310024		harryleee	Portal (BOI24_portal)	C++20	11 / 100	23 ms	3768 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5;
int n;
pair<int, int> a[maxn + 1];
vector<int> x, y;

bool check(pair<int, int> x, pair<int, int> y, pair<int, int> z){
    int a = x.second - y.second;
    int b = y.first - x.first;
    int c = (-a) * x.first + (-b) * x.second;
    return (a * z.first + b * z.second + c == 0);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].first >> a[i].second;
    }
    if (n <= 2){
        cout << -1;
        return 0;
    }
    else if (n == 3){
        if (check(a[1], a[2], a[3])){
            cout << -1;
            return 0;
        }

        int res = 0;
        a[4].first = a[3].first + (a[2].first - a[1].first);
        a[4].second = a[3].second + (a[2].second - a[1].second);

        sort(a + 1, a + 5, [](pair<int, int> u, pair<int, int> v){
            return u.first < v.first;
        });
        // for (int i = 1; i <= 4; ++i) cout << a[i].first << ' ' << a[i].second << '\n';
        // cout << '\n';

        int g = 0, opt = 0;
        for (int i = 2; i <= 4; ++i){
            g = gcd(g, a[i].first - a[i - 1].first);
        }
        if (a[2].first != a[1].first)
            opt = max(abs(a[2].second - a[1].second), abs(a[4].second - a[3].second)) + 1;
        else
            opt = max(abs(a[2].second - a[1].second), abs(a[4].second - a[3].second));
        // cout << g << ' ' << opt << '\n';
        res = max(res, g * opt);

        sort(a + 1, a + 5, [](pair<int, int> u, pair<int, int> v){
            return u.second < v.second;
        });
        g = 0, opt = 0;
        for (int i = 2; i <= 4; ++i){
            g = gcd(g, a[i].second - a[i - 1].second);
        }
        if (a[2].second != a[1].second)
            opt = max(abs(a[2].first - a[1].first), abs(a[4].first - a[3].first)) + 1;
        else
            opt = max(abs(a[2].first - a[1].first), abs(a[4].first - a[3].first));
        // cout << g << ' ' << opt << '\n';
        res = max(res, g * opt);

        cout << res << '\n';
        return 0;
    }
    else{
        for (int i = 1; i <= n; ++i){
            x.push_back(a[i].first); y.push_back(a[i].second);
        }
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        x.erase(unique(x.begin(), x.end()), x.end());
        y.erase(unique(y.begin(), y.end()), y.end());

        long long res1 = -1, res2 = -1;
        for (int i = 1; i < x.size(); ++i){
            if (res1 == -1) res1 = x[i] - x[i - 1];
            else res1 = gcd(res1, x[i] - x[i - 1]);
        }

        for (int i = 1; i < y.size(); ++i){
            if (res2 == -1) res2 = y[i] - y[i - 1];
            else res2 = gcd(res2, y[i] - y[i - 1]);
        }
        
        if (res1 == -1 || res2 == -1) cout << -1;
        else cout << 1LL * res1 * res2;
    }

    return 0;
}

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