[백준/Python] 1485 : 정사각형

 

import sys
from itertools import combinations
T = int(input())

def length(arr, distance): # 모든 변의 길이를 측정해서 오름차순 만들고 변/대각선 구분하기
    perm = list(combinations(arr , 2))
    for a , b in perm:
        distance.append((b[0]-a[0])*(b[0]-a[0]) + (b[1]-a[1])*(b[1]-a[1]))
    distance.sort()
    if distance[0] == distance[1] == distance[2] == distance[3] and distance[4] == distance[5]:
        print(1)
    else: print(0)

for i in range(T):
    arr = []       # 좌표 배열
    distance = []  # 변 & 대각선 길이 
    for j in range(4):
        a,b = map(int, sys.stdin.readline().split())
        arr.append((a,b))
    length(arr, distance)

 

일단 예제 입력만 봐도 입력 내용이 매우 많아보여서 효율을 위해 sys.stdin.readline()으로 입력받았으며, 지금 한 테스트케이스 T 당 4개의 좌표를 입력 받는 것이기 때문에 2중 반복문을 사용했음

 

초기 리스트로는 좌표들을 담아놓을 arr과 좌표들 간의 거리를 계산해서 저장해놓을 distance 리스트를 만들었고, 이들은 테스트케이스마다 재활용되어야 하기 때문에 겉 for문 안에다가 넣어서 매번 초기화되도록 하였다.

이렇게 하면 이후 해당 리스트들에 접근하거나 값을 저장할 때 굳이 for문 만들어서 arr[i][j] 이렇게 안하고 그냥 append() 써서 넣어주면 되기 때문에 효율적이다! (어차피 이 문제에서는 요소를 추출할 일이 없기 때문)

 

length() 라는 함수를 따로 만들었고, 여기서는 입력받은 좌표들 간의 모든 변의 길이들을 측정해서 해당 변이 대각선인지, 그냥 변인지 판단하여 정사각형 여부를 판단하게 된다.

 

정사각형 조건을 생각해보면 일단 1) 모든 변의 길이가 같아야 하며, 2) 두 대각선의 길이가 모두 같아야 한다.

그런데 지금 문제에서 좌표를 입력 받는 순서가 크기 순서가 아니라 랜덤이기 때문에 무작정 좌표 a와 좌표 b간의 거리를 측정하였을 때 이것이 변인지 대각선인지 멋대로 판단할 수 없다.

 

따라서 일단 조합을 이용해서 6쌍의 좌표 조합을 만들기 각각에 대한 길이를 모두 구하여 distance 리스트에 넣은 다음, 이를 오름차순으로 정렬하였다.

수학적으로 네 변의 길이가 두 대각선의 길이보다 작기 때문에 이 원리대로라면 오름차순으로 정렬했을 때 앞의 4개 숫자가 변의 길이, 뒤의 2개 숫자가 대각선의 길이가 될 것이라고 생각했음

 

이제 여기서 네 변의 길이가 서로 같은지, 그리고 두 대각선의 길이가 서로 같은지 if 문으로 판별하고 맞으면 1, 틀리면 0을 출력하도록 설정하고 마무리하였다.

 

 

어렵진 않지만 아이디어를 생각해내는게 포인트였던 문제였다~