제출 #1355843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355843		Aviansh	Portal (BOI24_portal)	C++20	1 / 100	2098 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];
    }
    ///origin shifted.
    int curx=0;
    int cury=0;
    int gx = 0;
    int gy = 0;
    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]);
        }
        if(pts[i][0]==0||pts[i][1]==0){
            if(pts[i][0]!=0){
                curx=gcd(curx,pts[i][0]);
            }
            else{
                cury=gcd(cury,pts[i][1]);
            }
            continue;
        }
    }
    if(curx==0||cury==0){
        cout << -1;
        return 0;
    }
    for(int i = 1;i<n;i++){
        if((curx==0||gcd(curx,gcd(pts[i][0],pts[i][1]))<curx)&&(cury==0||gcd(cury,gcd(pts[i][0],pts[i][1]))<cury)){
            for(int j = 1;j<n;j++){
                ///for finding dx
                int gc = gcd(abs(pts[i][1]),abs(pts[j][1]));
                if(gc){
                    int a = -((pts[j][1])/gc);
                    int b = (pts[i][1])/gc;
                    assert(a*pts[i][1]+b*pts[j][1]==0);
                    int dx = a*pts[i][0]+b*pts[j][0];
                    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(pts[j][0]));
                if(gc){
                    int a = -((pts[j][0])/gc);
                    int b = (pts[i][0])/gc;
                    assert(a*pts[i][0]+b*pts[j][0]==0);
                    int dy = a*pts[i][1]+b*pts[j][1];
                    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: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35