[Python 3] BOJ - 9015 "정사각형"

 # 문제 링크

https://www.acmicpc.net/problem/9015

9015번: 정사각형

 

 # 풀이

 개인적으로 이 문제의 핵심은 정사각형의 성질을 이해하는 것이라 생각한다. 정사각형은 모든 변의 길이가 같으며 각각의 내각이 90도로 모두 같은 사각형을 의미한다. 따라서, 시간복잡도를 고려하지 않고 정사각형을 판별하려면 단순히 4점을 뽑으면 된다. 3점을 뽑아도 역시 정사각형을 판별할 수 있다. 그러나 3점으로는 절대로 시간안에 정답을 구할 수 없다. N 제한이 3000이기 때문에 최대 $O(N^2)$의 시간 복잡도가 허용된다. 즉, 2점을 뽑고 남은 2점을 알아내야 한다

<그림 1. 임의의 정사각형>

 위 그림 1은 임의의 정사각형을 나타낸 그림이다. 빨간색 바깥쪽 사각형을 관찰하면 4개의 삼각형이 있다는 것을 알 수 있다. 이 때 4개의 삼각형 중 2개의 점은 검은색 정사각형의 임의의 2개의 점이다. 이 때, 그림 1에서처럼 $(x_1, y_1), (x_2, y_2)$을 기준으로 각각의 x값의 차이와 각각의 y값의 차이를 x_diff, y_diff라고 하자. 또한, 삼각형의 90도가 아닌 두 각을 각각 a와 b라고 하자. 

 그렇다면 현재 초록색 물음표와 같은 길이는 가지는 것은 x_diff임이 자명하다. 왜냐하면 $(x_2, y_2), (x_3, y_3)$을 기준으로 했을 때 $(x_2, y_2)$와 $(x_3, y_3)$을 이루는 직선과 초록색 물음표 직선이 이루는 각이 a이기 때문이다. 즉, 두 삼각형은 합동이기 때문이다. 따라서 같은 논리로, 파란색 물음표 직선의 길이는 y_diff와 길이가 같다. 따라서, 이미 고른 2개의 점이 아니면서 정사각형의 일부가 되는 나머지 두 점은 아래와 같이 표현될 수 있다. $$ (x_3, y_3) = (x_2 - y_{diff}, \ y_2 + x_{diff}) , \ \  (x_4, y_4) = (x_1 - y_{diff}, \ y_1 + x_{diff}) $$

 물론, 현재의 관계식은 $(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$가 서로 반시계 방향일 때 적용되며 당연히 시계 방향일 때는 관계식의 부호가 조금 달라지긴 하나 정답을 구할때 전혀 문제가 없다. 어느 방향이건 찾는 두 점이 주어진 입력의 점들의 집합에 있는지 없는지만 빠르게 확인하면 된다. 따라서 set을 적절히 이용하면 두 점을 찾는데 $O(1)$만에 판별할 수 있다. 만약 두 점이 set에 있다면 정사각형의 넓이를 정답에 갱신시켜준다.

 직사각형일 때는 위의 논리가 성립하지 않음을 직관적으로 알 수 있다. 그렇다면 마름모의 경우는 어떠할까? 결론적으로는 역시 성립하지 않는다. 왜냐하면 위 논리에서 핵심이 되었던 빨간 4개의 삼각형이 서로 합동이라는 조건을 만족하지 않기 때문이다. 왜냐하면 마름모의 내각이 모두 같지 않으면서 4변의 길이가 같은 사각형이기 때문이다.

 

 # 코드

import sys

# tc : 테스트케이스의 수
tc = int(sys.stdin.readline())
for _ in range(tc):
    # 입력부
    n = int(sys.stdin.readline())
    # cache : 입력으로 주어지는 점들의 집합
    cache = set()
    arr = []
    ans = 0
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        cache.add((a, b))
        arr.append((a, b))
        
    # 두 점을 뽑는다
    for i in range(n):
        for j in range(n):
            # 같은 점이라면 continue
            if i == j:
                continue
            x1, y1 = arr[i]
            x2, y2 = arr[j]
            # 현재 최대 넓이보다 작거나 같으면 continue
            if ans >= (x1 - x2) ** 2 + (y1 - y2) ** 2:
                continue
            x_diff, y_diff = x1 - x2, y1 - y2
            # 두 점이 cache에 있는지 없는지 판단
            if (x1 - y_diff, y1 + x_diff) in cache and (x2 - y_diff, y2 + x_diff) in cache:
                ans = max(ans, (x1 - x2) ** 2 + (y1 - y2) ** 2)
    # 정답 출력
    print(ans)