[백준] 4105 - 유클리드 (Python)

https://www.acmicpc.net/problem/4105

import sys
from itertools import batched
x, y = 0, 1

while True:
    points = list(map(float, sys.stdin.readline().split()))
    if points == [0.0]*12:
        break

    A, B, C, D, E, F = batched(points, 2)

    s = abs((D[x]*E[y]+E[x]*F[y]+F[x]*D[y])-(E[x]*D[y]+F[x]*E[y]+D[x]*F[y]))*0.5
    
    a = (C[x]-A[x], C[y]-A[y])
    b = (B[x]-A[x], B[y]-A[y])
    
    k = s/abs((a[x]*b[y])-(a[y]*b[x]))
    
    h = (k*a[x]+A[x], k*a[y]+A[y])
    g = (h[x]+b[x], h[y]+b[y])
    
    print(f'{g[x]:.03f} {g[y]:.03f} {h[x]:.03f} {h[y]:.03f}')

1) 아이디어

다음 조건을 만족하는 점H와 G의 좌표를 찾는다.

1. H는 점A에서 C로 뻗어가는 반직선 위에 있다.
2. ABGH는 평행사변형이다.
3. 평행사변형 ABGH의 넓이는 삼각형 DEF의 넓이와 같다.

주어진 그림에서 면적이 같아야 하는 부분을 표시하면 다음과 같다.

1. 먼저 삼각형 DEF는 세 점의 좌표를 이용해 구할 수 있다.
2. G와 H를 구하기 위해서, 벡터의 외적을 사용한다.
   두 백터의 외적은 서로 다른 두 벡터 사이에 만들어지는 평행사변형의 면적과 같으므로, 평행사변형 ABGH의 넓이는 벡터 AH와 벡터 AB의 외적으로 계산할 수 있다.
3. 한편 점 H는 반직선 AC상에 있기 때문에 벡터 AH는 벡터 AC의 실수배 백터이다. 따라서 벡터 AB와 AC의 외적과 삼각형 DEF의 면적을 같게 만들어주는 실수를 찾으면 H를 구할 수 있다.
4. 점 G는 벡터 AB와 벡터 AH의 합으로 구할 수 있다.

2) 풀이

각 케이스에 대해 실수 12개가 입력으로 주어진다. 모든 점이 0.0으로 주어진 경우 종료한다.
각 점의 좌표를 튜플로 관리하기 위해 itertools 모듈의 batched를 사용했다. batched는 분할하고자 하는 이터레이션과 각 원소의 길이 n을 인자로 받는다.

A, B, C, D, E, F = batched(points, 2)

위 라인은 입력된 12개의 실수 이터레이션 points를 다음과 같이 분할해 반환한다.

# 입력
[1.3, 2.6, 12.1, 4.5, 8.1, 13.7, 2.2, 0.1, 9.8, 6.6, 1.9, 6.7]

# 반환(n=2)
[(1.3, 2.6), (12.1, 4.5), (8.1, 13.7), (2.2, 0.1), (9.8, 6.6), (1.9, 6.7)]

Python Documentation - itertools

1. 삼각형 DEF의 면적

주어진 D, E, F의 좌표를 사용해 삼각형의 면적 s를 구한다.
(사선공식 또는 신발끈공식, 가우스 면적공식 등등...)

s = abs( (D[x]*E[y] + E[x]*F[y] + F[x]*D[y]) - (E[x]*D[y] + F[x]*E[y] + D[x]*F[y]) ) * 0.5

2. AB와 AC의 외적

벡터 AB와 AC를 다음과 같이 a와 b로 선언한다.

a = (C[x]-A[x], C[y]-A[y])
b = (B[x]-A[x], B[y]-A[y])

$k$$\overrightarrow{a}\times\overrightarrow{b}$$=s$를 만족하는 $k$를 찾는다.
$\overrightarrow{a}=(a_x, a_y)$이고 $\overrightarrow{b}=(b_x, b_y)$일때, $k$$\overrightarrow{a}\times\overrightarrow{b}$는 $k(a_x b_y - a_y b_x)$로 전개된다.

k = s / abs( (a[x]*b[y]) - (a[y]*b[x]) )

3. 점 H 구하기

벡터a를 k배 한 후,시작점을 A로 평행이동한다.

h = (k*a[x]+A[x], k*a[y]+A[y])

4. 점 G 구하기

벡터의 합의 성질에 따라 다음과 같으므로 점 G의 좌표를 구할 수 있다.

g = (h[x]+b[x], h[y]+b[y])

필요한 모든 좌표를 구했으므로 문제가 요구하는 방식에 따라 포맷팅해 출력한다.

print(f'{g[x]:.03f} {g[y]:.03f} {h[x]:.03f} {h[y]:.03f}')