BOJ 2415 - 직사각형

문제 링크 : https://www.acmicpc.net/problem/2415

문제 소개

좌표평면에 점들이 주어지면 주어진 점들로 만들 수 있는 가장 큰 직사각형의 크기를 출력하는 문제이다. 

문제 풀이

굉장히 아이디어성 문제이고, 다양한 풀이가 나올 수 있는 문제이다. 일단 이 문제를 풀기 위해서 직사각형의 성질들을 생각해보자.

- 두 쌍의 대변의 길이가 각각 같다.
- 두 쌍의 대각의 크기가 각각 같다.
- 두 대각선이 서로 다른 대각선을 이등분 한다.
- 두 대각선의 길이가 같다.

한 직사각형에서 변이나 길이는 두 쌍이지만, 대각선은 두 개이다. 따라서 대각선에 집중을 해보자. 두 대각선의 길이가 같고, 서로 이등분하면 직사각형이다. 즉, $N^2$개의 선을 만들 수 있고, 그 중 길이가 같고 서로 이등분 하는 두 선을 잡아서 그 두 선을 이루는 4개의 점이 이루는 직사각형의 넓이를 확인하면된다. 

그렇다면 대각선들이 길이가 같고 서로 이등분 하는지에 대하여 확인을 해야한다. 일단 두 점 사이의 거리로 선의 길이를 알 수 있으며, 두 선분이 서로 이등분한다는 것은 두 선분의 중점이 같다는 것을 의미하기 때문에 임의의 두 점으로 만든 각 선분에 대해서 길이와 중점을 저장해 놓으면 된다. 

두 대각선이 조건을 만족하는 지 확인하기 위해서는 중점의 x좌표, 중점의 y좌표, 선분의 길이에 대해서 정렬을 해준 후 세 값이 모두 같은 선분 쌍에 대해서 네 점의 직사각형의 넓이를 재면 된다. 빠지는 경우가 없도록 해야한다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
struct poi{
    ll dis,x,y;
    int numa,numb;
};
 
poi arr[1010101];
poi lin[3010101];
 
ll getdis(poi a,poi b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
 
ll siz(poi a,poi b,poi c,poi d){
    return abs(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y))+ abs(a.x*(b.y-d.y)+b.x*(d.y-a.y)+d.x*(a.y-b.y));
}
 
bool sf(poi a,poi b){
    if(a.dis!=b.dis) return a.dis<b.dis;
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
        scanf("%lld %lld",&arr[i].x,&arr[i].y);
    ll cnt=0;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++){
            cnt++;
            lin[cnt]={getdis(arr[i],arr[j]),arr[i].x+arr[j].x,arr[i].y+arr[j].y,(int)i,(int)j};
        }
    sort(lin+1,lin+1+cnt,sf);
    ll ans=0;
    for(i=1;i<cnt;i++){
        ll fl=i+1;
        while(lin[i].dis==lin[fl].dis&&lin[i].x==lin[fl].x&&lin[i].y==lin[fl].y){
            ans=max(ans,siz(arr[lin[i].numa],arr[lin[i].numb],arr[lin[fl].numa],arr[lin[fl].numb]));
            fl++;
        }
    }
    printf("%lld",ans/2);
}