[python] 백준 11664 선분과 점

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

11664번: 선분과 점

 

 

문제 해결

3차원 공간에서 선분 AB와 점 C를 가장 가까운 직선을 그릴 때 2가지 경우가 나온다.

수직으로 만나거나

일직선으로 만나거나

두 가지 경우를 나눠서 측정할 수 있지만 (cosin 값을 이용해 두 분류를 구분할 수 있다.) 그래도 최소 거리를 구한다는 것이 쉽지 않다.

우리는 극한을 이용해서 구할 것이다.

점 C에서 선분 AB사이의 거리를 answer라 했을 때 answer≤ min(ac, bc) 일 것이다.

선분 AB의 중심을 점 m이라 할 때 점 m에서 점 C까지 거리를 h라 할 때 h≤min(ac,bc)일 것이다.

ac, bc 중 긴 선분의 길이가 있을 것이다. ac가 길면 점 a를 점 m으로 옮기고 다시 점 m을 점 a와 점 b의 중심으로 정의한다. 계속 다음과 같이 h를 조절하여 변화가 $10^{-6}$보다 작을 때 그 값을 answer라 놓는다.

점차 가장 가까운 길이에 수렴할 것이다.

 

CODE

import sys
input = sys.stdin.readline
import math
def solution(ax, ay, az, bx, by, bz, cx, cy, cz):
    target = float('inf')
    ac = math.sqrt((ax-cx)**2 + (ay-cy)**2 + (az-cz)**2)
    bc = math.sqrt((bx-cx)**2 + (by-cy)**2 + (bz-cz)**2)

    while True:
        mx, my, mz = (ax+bx)/2, (ay+by)/2, (az+bz)/2
        h = math.sqrt((mx-cx)**2 + (my-cy)**2 + (mz-cz)**2)

        if abs(target-h) <=1e-6:
            return round(target,6)
        target = min(target,h)
        if h < target:
            target = h
        elif ac > bc:
            ax, ay, az = mx, my, mz
            ac = h
        else:
            bx, by, bz = mx, my, mz
            bc = h

if __name__=='__main__':
    ax, ay, az, bx, by, bz, cx, cy, cz = map(int, input().split())
    answer = solution(ax, ay, az, bx, by, bz, cx, cy, cz)
    print(answer)