Submission #1355996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355996		Aviansh	Portal (BOI24_portal)	C++20	55 / 100	2096 ms	1860 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    array<int,2>pts[n];
    for(int i = 0;i<n;i++){
        cin >> pts[i][0];
        cin >> pts[i][1];
    }
    for(int i = n-1;i>=0;i--){
        pts[i][0]-=pts[0][0];
        pts[i][1]-=pts[0][1];
    }
    int curx=0;
    int cury=0;
    int gx = 0;
    int gy = 0;
    ///origin shifted.
    for(int i = 1;i<n;i++){
        if(pts[i][0]!=0){
            gx=gcd(gx,pts[i][0]);
        }
        if(pts[i][1]!=0){
            gy=gcd(gy,pts[i][1]);
        }
        for(int z = 1;z<i;z++){
            if(gcd(gcd(pts[i][0],pts[i][1]),curx)==curx&&gcd(gcd(pts[i][0],pts[i][1]),cury)==cury){
                break;
            }
            int tx = pts[z][0];
            int ty = pts[z][1];
            ///for finding dx
            int gc = gcd(abs(pts[i][1]),abs(ty));
            if(gc){
                int a = -((ty)/gc);
                int b = (pts[i][1])/gc;

                int dx = a*pts[i][0]+b*tx;
                dx=abs(dx);
                if(curx==0){
                    curx=dx;
                }
                else if(dx!=0){
                    curx=gcd(curx,dx);
                }
            }
            ///for finding dy
            gc = gcd(abs(pts[i][0]),abs(tx));
            if(gc){
                int a = -((tx)/gc);
                int b = (pts[i][0])/gc;

                int dy = a*pts[i][1]+b*ty;
                dy=abs(dy);
                if(cury==0){
                    cury=dy;
                }
                else if(dy!=0){
                    cury=gcd(cury,dy);
                }
            }
        }
    }
    if(curx==0||cury==0){
        cout << -1;
    }
    else{
        if(gx==0||gy==0){
            cout << -1;
        }
        else{
            cout << max(curx*gy,cury*gx);
        }
    }
    return 0;
}

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