[백준] #1485 정사각형(python)

📌문제

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

입력

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

출력

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

예제 입력

2
1 1
1 2
2 1
2 2
2 2
3 3
4 4
5 5

예제 출력

1
0

백준 1485번 문제

💡Idea

간단해보이지만 꽤 헤맸던 문제입니다😥

정사각형🟥의 정의를 먼저 살펴보면 아래와 같습니다.

정사각형은 네 변의 길이가 모두 같고, 네 각의 크기가 모두 같은 사각형이다.

처음에 저는 네 각의 크기가 모두 같다는 정의를 이용하여 문제에 접근해보았습니다.

하지만 정사각형에는 간과했던 성질이 하나 더 있습니다.

정사각형의 두 대각선 길이는 서로 같다.

따라서, 네 점을 잇는 6개의 선들의 길이를 모두 구한 뒤, 4개의 선이 동일하고 나머지 2개의 선이 서로 동일한지를 확인하면 쉽게 문제를 해결할 수 있습니다.

💻코드

• ⏰ 시간 : 68 ms / 메모리 : 34076 KB

import itertools
import sys
from collections import Counter

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    length = [] # 6개의 길이 저장 리스트
    vertex = [list(map(int, input().split())) for __ in range(4)]
    for first, second in itertools.combinations(vertex, 2): # 두 점을 선택하여 이은 선의 길이 계산
        length.append((((first[0] - second[0]) ** 2) + ((first[1] - second[1]) ** 2)))
    counters = (Counter(length)).values() # 선의 종류가 2이고, 각각 4개, 2개의 개수를 가지면 정사각형
    if len(counters) == 2 and 4 in counters and 2 in counters:
        print(1)
    else:
        print(0)