문제 링크
문제 요약
두 개의 삼각형이 주어졌을 때, 이 두 삼각형이 서로 닮음인지 판별하고, 닮음이라면 첫 번째 삼각형이 두 번째 삼각형보다 몇 배 큰지(닮음비)를 출력하는 문제입니다.
- 만약 닮음이 아니라면 -1을 출력합니다.
- 삼각형의 각 꼭짓점은 x, y 좌표로 주어지며, 입력 순서는 시계 방향이든 반시계 방향이든 무관합니다.
- 주어지는 점들은 항상 삼각형을 이룹니다 (겹치거나 일직선상에 있지 않음).
- 닮음비는 실수로 출력하며, 최소 0.0001의 정밀도를 요구합니다.
풀이
두 삼각형이 닮음인지 판별하고 닮음비를 구하는 문제의 핵심은 삼각형의 세 변의 길이를 활용하는 것입니다. 두 삼각형이 닮음이기 위해서는 대응하는 세 변의 길이의 비가 일정해야 합니다.
-
변의 길이 계산:
- 각 삼각형에 대해 세 변의 길이를 계산합니다. 두 점 과 사이의 거리는
sqrt((x_1-x_2)^2 + (y_1-y_2)^2)입니다. - 하지만 실수 연산의 정밀도 문제를 최소화하기 위해, 실제 변의 길이 대신 변의 길이의 제곱을 계산하여 사용합니다. 즉,
(x_1-x_2)^2 + (y_1-y_2)^2값을 사용합니다.
- 각 삼각형에 대해 세 변의 길이를 계산합니다. 두 점 과 사이의 거리는
-
정렬:
- 입력으로 주어지는 꼭짓점의 순서는 무작위이므로, 어떤 변이 다른 삼각형의 어떤 변에 대응되는지 알 수 없습니다.
- 이를 해결하기 위해, 각 삼각형의 세 변의 길이의 제곱 값을 오름차순으로 정렬합니다. 이렇게 하면 가장 짧은 변의 제곱은 가장 짧은 변의 제곱에, 중간 변의 제곱은 중간 변의 제곱에, 가장 긴 변의 제곱은 가장 긴 변의 제곱에 대응될 것이라고 가정할 수 있습니다.
-
닮음 여부 확인:
- 첫 번째 삼각형의 정렬된 변의 길이 제곱 값을
A = [A0, A1, A2](A0 ⇐ A1 ⇐ A2), 두 번째 삼각형의 정렬된 변의 길이 제곱 값을B = [B0, B1, B2](B0 ⇐ B1 ⇐ B2)라고 합시다. - 두 삼각형이 닮음이려면 대응하는 변들의 길이의 비가 일정해야 합니다. 즉,
sqrt(A0)/sqrt(B0) = sqrt(A1)/sqrt(B1) = sqrt(A2)/sqrt(B2)여야 합니다. - 이 식의 양변을 제곱하면
A0/B0 = A1/B1 = A2/B2와 같아집니다. - 나눗셈을 직접 사용하는 대신, 부동 소수점 오차와 0으로 나누는 상황을 피하기 위해 교차 곱셈(cross-multiplication) 방식을 사용합니다.
A0/B0 = A1/B1은A0 * B1 = A1 * B0와 같습니다.A1/B1 = A2/B2은A1 * B2 = A2 * B1와 같습니다.
- 이 두 조건이 모두 참이면 두 삼각형은 닮음입니다. (문제 조건에 따라 점들이 항상 삼각형을 이루므로 변의 길이가 0인 경우는 없습니다.)
- 첫 번째 삼각형의 정렬된 변의 길이 제곱 값을
-
닮음비 계산:
- 두 삼각형이 닮음이라면, 닮음비
k는sqrt(A0 / B0)(또는sqrt(A1 / B1),sqrt(A2 / B2))로 구할 수 있습니다. - 어떤 변을 사용하든 값이 같게 나오게 됩니다.
- 두 삼각형이 닮음이라면, 닮음비
정답 코드
# 삼각형의 세 변의 길이의 제곱을 계산하여 정렬된 리스트로 반환
def f(l: list):
ret = []
for i in range(3):
x, y = l[2 * i], l[2 * i + 1] # 현재 꼭짓점 (x, y)
nx, ny = l[(2 * (i + 1)) % 6], l[(2 * (i + 1)) % 6 + 1] # 다음 꼭짓점 (nx, ny)
# 두 점 사이의 거리의 제곱 계산: (x1-x2)^2 + (y1-y2)^2
ret.append((x - nx) ** 2 + (y - ny) ** 2)
return sorted(ret) # 계산된 세 변의 길이의 제곱을 오름차순 정렬
# 두 삼각형의 닮음비를 계산
def similar_rate(A: list, B: list):
if A[0] * B[1] == A[1] * B[0] and A[1] * B[2] == A[2] * B[1]:
return sqrt(A[0] / B[0])
return -1 # 닮음이 아니면 -1 반환
def solve():
A_coords = [*map(int, input().split())] # 첫 번째 삼각형의 꼭짓점 좌표
B_coords = [*map(int, input().split())] # 두 번째 삼각형의 꼭짓점 좌표
A_squared_lengths = f(A_coords) # 첫 번째 삼각형의 변 길이 제곱 리스트
B_squared_lengths = f(B_coords) # 두 번째 삼각형의 변 길이 제곱 리스트
# 계산된 변 길이 제곱 리스트를 사용하여 닮음비 계산 및 출력
print(similar_rate(A_squared_lengths, B_squared_lengths))
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()