Submission #1329679

#TimeUsernameProblemLanguageResultExecution timeMemory
1329679ErJPortal (BOI24_portal)C++20
11 / 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

pp vec(pp vecA, pp vecB){
    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};
    return vecC;
}

pp vec2(pp vecA, pp vecB){
    ll g = gcd(vecA.second, vecB.second);
    ll alpha = vecB.second / g;
    ll beta = -vecA.second / g;
    pp vecC = {alpha * vecA.first + beta * vecB.first, 0};
    return vecC;
}

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 == 2){
        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;
    }
    if(n < 2001){
        ll XG = point[0].first - point[1].first;
        ll YG = point[0].second - point[1].second;
        for(int i = 0; i < point.size(); i++){
            for(int j = i + 1; j < point.size(); j++){
                XG = gcd(XG, point[i].first - point[j].first);
                YG = gcd(YG, point[i].second - point[j].second);
            }
        }

        ll ans = -1;
        ll row = 0;
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(i == j || k == j || k == i) continue;
                    pp vecA = {point[i].first - point[j].first, point[i].second - point[j].second};
                    pp vecB = {point[i].first - point[k].first, point[i].second - point[k].second};
                    if(vecA.first == 0) {
                        ll val = vecA.second;
                        if(row == 0) row = val;
                        else row = gcd(row, val);
                    }
                    if(vecB.first == 0) {
                        ll val = vecB.second;
                        if(row == 0) row = val;
                        else row = gcd(row, val);
                    }
                    if(vecA.first == 0 || vecB.first == 0) continue;
                    pp vecC = vec(vecA, vecB);
                    if(row == 0) row = vecC.second;
                    else row = gcd(row, vecC.second);
                }
            }
        }
        ans = max(ans, row * XG);

        ll col = 0;
        for(int i = 0; i < 10; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(i == j || k == j || k == i) continue;
                    pp vecA = {point[i].first - point[j].first, point[i].second - point[j].second};
                    pp vecB = {point[i].first - point[k].first, point[i].second - point[k].second};
                    if(vecA.second == 0) {
                        ll val = vecA.first;
                        if(row == 0) row = val;
                        else row = gcd(row, val);
                    }
                    if(vecB.second == 0) {
                        ll val = vecB.first;
                        if(row == 0) row = val;
                        else row = gcd(row, val);
                    }
                    if(vecA.second == 0 || vecB.second == 0) continue;
                    pp vecC = vec2(vecA, vecB);
                    if(col == 0) col = vecC.first;
                    else col = gcd(col, vecC.first);
                }
            }
        }
        ans = max(ans, col * YG);
        if(ans == 0){
            cout << -1 << '\n';
        }else{
            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...