Note
2D 평면 위 네 점이 정사각형을 이루는지 판별할 때, 무게중심에서 네 점까지의 거리와 외접 직사각형의 가로·세로를 이용하는 원리입니다.
문제 상황
네 점 p1, p2, p3, p4의 좌표가 순서 없이 주어질 때, 이 네 점으로 정사각형이 만들어지는지 판별합니다.
- 정사각형: 네 변의 길이가 같고, 네 각이 모두 90도
- 점의 순서는 정해져 있지 않음
핵심 아이디어
1. 네 점이 서로 다름
같은 좌표가 있으면 정사각형이 될 수 없으므로, 네 점이 서로 다른 점인지 먼저 확인합니다.
2. 무게중심(centroid)
네 점의 무게중심은 좌표의 평균입니다.
- center_x = (x1 + x2 + x3 + x4) / 4
- center_y = (y1 + y2 + y3 + y4) / 4
정사각형에서는 대각선의 교점이 무게중심과 같고, 네 꼭짓점은 모두 무게중심에서 같은 거리에 있습니다.
(마름모는 대각선 교점에서 네 점까지의 거리가 두 쌍으로만 같고, 정사각형만 네 개 모두 같음)
3. 무게중심에서의 거리
무게중심에서 각 점까지의 거리(또는 거리 제곱) 를 구해, 네 값이 모두 같고 0이 아니면 (한 점이 무게중심과 겹치지 않으면) “네 점이 한 원(중심이 무게중심) 위에 있고, 중심에 점이 없다”는 뜻이 됩니다.
정사각형이면 이 조건을 만족합니다.
4. 외접 직사각형이 정사각형
네 점의 x 최소·최대, y 최소·최대로 만드는 외접 직사각형을 생각합니다.
정사각형이면 이 직사각형의 가로 길이와 세로 길이가 같아야 합니다.
(직사각형이지만 정사각형이 아닌 경우는 가로 ≠ 세로이므로 걸러짐)
알고리즘 흐름
- 네 점이 서로 다른지 set으로 확인 (크기 4)
- 무게중심 (네 좌표의 평균) 계산
- 외접 직사각형 min_x, max_x, min_y, max_y 계산 후 (max_x - min_x) == (max_y - min_y) 인지 확인
- 무게중심에서 각 점까지 거리 제곱을 구해, 네 값이 모두 같고 0이 아닌지 확인
- 위를 모두 만족하면 True, 아니면 False
왜 거리 제곱을 쓰나?
거리 대신 거리 제곱을 써도 “네 값이 같은지”만 보면 되므로 비교가 더 단순합니다.
(제곱근을 쓰지 않아 부동소수 오차도 줄일 수 있음)
요약
| 조건 | 의미 |
|---|---|
| 서로 다른 네 점 | 중복 좌표 제거 |
| 무게중심에서 네 점까지 거리(제곱) 동일 | 정사각형의 대각선 교점 성질 |
| 거리 > 0 | 한 점이 중심과 겹치지 않음 |
| 외접 직사각형 가로 == 세로 | 정사각형만 허용 (일반 직사각형 제외) |
관련 문제
- LeetCode 593: Valid Square - 코드 구조 설명