Submission #1329660

#TimeUsernameProblemLanguageResultExecution timeMemory
1329660ErJPortal (BOI24_portal)C++20
21 / 100
30 ms1860 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define inf 1000000000
#define mod 1000000007

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n;
    cin >> n;
    
    vp point(n);
    for(int i = 0; i < n; i++){
        cin >> point[i].first >> point[i].second;
    }
    if(n <= 2) {
        cout << -1 << '\n';
        return 0;
    }
    if(n == 3){
        ll YG = gcd(point[0].second - point[1].second, gcd(point[0].second - point[2].second, point[1].second - point[2].second));
        ll XG = gcd(point[0].first - point[1].first, gcd(point[0].first - point[2].first, point[1].first - point[2].first));
        pp vecA = {point[0].first - point[1].first, point[0].second - point[1].second};
        pp vecB = {point[0].first - point[2].first, point[0].second - point[2].second};
        ll g = gcd(vecA.first, vecB.first);
        ll alpha = vecB.first / g;
        ll beta = -vecA.first / g;
        pp vecC = {0, alpha * vecA.second + beta * vecB.second};
        ll ans = -1;
        ans = max(ans, vecC.second * XG);

        g = gcd(vecA.second, vecB.second);
        alpha = vecB.second / g;
        beta = -vecA.second / g;
        vecC = {alpha * vecA.first + beta * vecB.first, 0};
        ans = max(ans, vecC.first * YG);
        
        if(ans == 0){
            cout << -1 << '\n';
            return 0;
        }
        cout << ans << '\n';
        return 0;
    }
    sort(point.begin(), point.end());
    ll row = 0;
    for(int i = 1; i < n; i++){
        if(point[i].first == point[i - 1].first){
            ll val = point[i].second - point[i - 1].second;
            if(row == 0) row = val;
            row = gcd(row, val);
        }
    }
    for(int i = 0; i < n; i++) swap(point[i].first, point[i].second);
    sort(point.begin(), point.end());
    ll col = 0;
    for(int i = 1; i < n; i++){
        if(point[i].first == point[i - 1].first){
            ll val = point[i].second - point[i - 1].second;
            if(col == 0) col = val;
            col = gcd(col, val);
        }
    }
    if(row == 0 || col == 0){
        cout << -1 << '\n';
        return 0;
    }
    cout << row * col << '\n';
}
#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...