수천개의 점들 중에서 가장 넓이가 큰 정사각형을 찾는 방법

9015번: 정사각형

 

점이 n개 <= 3000가 있을 때 가장 넓이가 큰 정사각형을 찾는 문제

 

그냥 한다면 O(N^4)이겠지만 당연히 안될거고

 

O(N^3)인 방법도 있긴한데 N <= 3000이다보니 어렵다

 

정사각형 성질을 이용하면.. 임의의 두 점 A(x1,y1), B(x2,y2)을 먼저 잡고 벡터 AB를 구한다

 

벡터 AB = OB - OA = (x2-x1, y2-y1)으로 구할 수 있다

 

 

 

다음 벡터 AB를 시계방향으로 90도 회전하면 벡터 AD를 구할 수 있다

 

90도 회전하는 방법은?

 

(x,y) >> (-y,x)로 되므로 벡터 AD = (-y2+y1, x2-x1)이 된다

 

https://deepdata.tistory.com/1388

 

 

 

 

만약 D의 좌표를 (x',y')이라고 하면, 벡터 AD = (y1-y2, x2-x1)이므로, 

 

(x'-x1, y'-y1) = (y1-y2,x2-x1)이므로, x' = x1 + (y1-y2), y' = y1 + (x2-x1)으로 구할 수 있다

 

그리고 벡터 AD는 평행이동하면... 벡터 BC가 된다.

 

 

 

따라서 C의 좌표가 (x',y')이라면 (x'-x2, y'-y2) = (y1-y2, x2-x1)이므로,

 

x' = x2 + (y1-y2), y' = y2+(x2-x1)이다.

 

그러므로 (x1,y1), (x2,y2)를 알고 있다면 정사각형을 이루는 나머지 두 점을 구할 수 있다.

 

그래서 (x1,y1), (x2,y2)를 잡고 나머지 두 점을 구한 다음, 이 나머지 두 점이 평면상에 실제로 존재하는지 hash로 체크하면 된다

 

from sys import stdin

T = int(stdin.readline())

for _ in range(T):
    
    n = int(stdin.readline())

    A = []
    H = {}

    for _ in range(n):
        
        x,y = map(int,stdin.readline().split())

        A.append((x,y))
        H[(x,y)] = 1
    
    answer = 0

    for i in range(n):
        
        x1,y1 = A[i]

        for j in range(n):
            
            x2,y2 = A[j]

            if i == j:
                
                continue

            v = (x2-x1,y2-y1)
            vv = (-v[1],v[0])

            x3,y3 = x2-v[1],y2+v[0]
            x4,y4 = x1-v[1],y1+v[0]

            if H.get((x3,y3),0) == 1 and H.get((x4,y4),0) == 1:
                
                s = v[0]**2 + v[1]**2

                if answer < s:
                    
                    answer = s

    print(answer)

 

 

여기서 정사각형 넓이는.. 벡터 (x2-x1, y2-y1)의 크기 제곱과 같기 때문에.. 루트를 취하지 않아도

 

정수형 연산으로 구할 수 있다는거