[Silver III] 정사각형 - 1485 (기하학, 정렬)

[Silver III] 정사각형 - 1485

문제 링크

성능 요약

메모리: 30840 KB, 시간: 80 ms

분류

기하학(geometry), 정렬(sorting)

문제 설명

네 점이 주어졌을 때, 네 점을 이용해 정사각형을 만들 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 네 줄로 이루어져 있으며, 점의 좌표가 한 줄에 하나씩 주어진다. 점의 좌표는 -100,000보다 크거나 같고, 100,000보다 작거나 같은 정수이다. 같은 점이 두 번 이상 주어지지 않는다.

출력

각 테스트 케이스마다 입력으로 주어진 네 점을 이용해서 정사각형을 만들 수 있으면 1을, 없으면 0을 출력한다.

 

처음 이 문제를 접근했을 때, 오름차순으로 정렬하여 x좌표가 같을 경우 y좌표의 차와 y좌표가 같을 경우 x좌표의 차만 같으면 정사각형이 만들어진다고 생각했다.

그러나, 정사각형이 평면 그대로 있지 않고,

정사각형

이런식으로 좌표가 막 찍혀있을 수도 있는 경우가 있었다. 그래서 수학적 공식이 필요하다 생각했지만, 아이디어가 잘 떠오르지 않아 구글링 풀이를 참고했다.

해결 방법은 가로, 세로 변의 모든 길이가 같은지, 대각선 길이가 같은지 모두 비교해주어야 했다.

두 가지 풀이가 있으며, 두 번째 풀이는 반복문으로 코드를 줄일 수 있었다.

import sys
t = int(sys.stdin.readline())
for i in range(t):
    c = []
    for j in range(4):
        x, y = list(map(int,sys.stdin.readline().split()))
        c.append((x, y))
    c.sort()

    side_one = (c[0][0] - c[1][0])**2 + (c[0][1] - c[1][1])**2
    side_two = (c[1][0] - c[3][0])**2 + (c[1][1] - c[3][1])**2
    side_three = (c[3][0] - c[2][0])**2 + (c[3][1] - c[2][1])**2
    side_four = (c[2][0] - c[0][0])**2 + (c[2][1] - c[0][1])**2
    edge_one = (c[0][0] - c[3][0])**2 + (c[0][1] - c[3][1])**2
    edge_two = (c[2][0] - c[1][0])**2 + (c[2][1] - c[1][1])**2
    
    if side_one != side_two or side_two != side_three or side_three != side_four or edge_one != edge_two or side_one + side_two != edge_one:
        print(0)    
    else:
        print(1)

import sys
input=sys.stdin.readline

N=int(input())

for i in range(N):
    # dot : 정사각형 좌표를 담은 리스트
    dot=[list(map(int,input().split())) for _ in range(4)]
    L=list()
    for i in range(3):
        for j in range(i+1,4):
            L.append((dot[i][0]-dot[j][0])*(dot[i][0]-dot[j][0])+(dot[i][1]-dot[j][1])*(dot[i][1]-dot[j][1]))
    L.sort()
    if L[0]==L[1] and L[0]==L[2] and L[0]==L[3] and L[4]==L[5]:
        print(1)
    else:
        print(0)

참고 풀이 : https://pslog-eraser.tistory.com/23 https://plein-de-verite.tistory.com/275