네 점이 주어졌을 때, 네 점을 이용해 정사각형을 만들 수 있는지 없는지 판별하는 문제다.
ccw 를 이용해 한 점을 잡아 각도가 작은 순으로 정렬 후 정사각형임을 판별할 수도 있지만, 판별하는 대상이 정사각형이기 때문에, 단순정렬만 이용해도 풀이가 가능하다.
2차원 평면 상에서 정사각형은 다음과 같이 나타낼 수 있다.
정사각형을 판별하기 위해 두 가지 조건을 만족하는지 확인한다.
- 네 변의 길이가 같다
- 두 대각선의 길이가 같다.
따라서 한 점을 기준으로 나머지 점들의 좌표를 시계 또는 반시계 방향으로 정렬한 뒤, 네 변의 길이와 두 대각선의 길이가 같은지 판별한다.
입력으로 받은 점들을 배열에 넣고, 점들을 x 좌표, y 좌표 순으로 정렬하고, 맨 처음 점을 기준점 p 로 놓는다. x 좌표가 가장 작고, x 좌표가 같다면 y 좌표가 작은 점이 p 로 선택될 것이다. 그림에 붙은 번호는 배열 요소들의 인덱스다.
니머지 점들을 시계 또는 반시계 방향으로 정렬되도록 하려면 2번 점과 3번 점의 위치를 변경하면 된다.
점들이 정렬 되었으니, 시계방향 또는 반시계방향으로 반복문을 돌리면서 네 변의 길이가 모두 같은지 체크한다.
p-점2, 점1-점3 의 대각선 길이가 같은지 확인한다.
코드는 다음과 같다.
from sys import stdin
def distance(p1,p2):
return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2
T = int(stdin.readline())
for _ in range(T):
arr = []
for _ in range(4):
x,y = map(int,stdin.readline().split())
arr.append((x,y))
arr.sort()
# 가장 x 좌표가 작은 점, x 좌표가 같다면 y 좌표가 작은 점
p = arr[0]
# 반시계 방향으로 정렬
arr[2],arr[3] = arr[3],arr[2]
# 변의 길이
d = distance(p,arr[1])
# 대각선의 길이
l = distance(p,arr[2])
ans = 1
for i in range(1,4):
if d != distance(arr[i],arr[(i+1)%4]):
ans = 0
if l != distance(arr[1],arr[3]):
ans = 0
print(ans)