[Python] 백준 11662번 : 민호와 강호

문제

민호와 강호가 2차원 좌표 평면 위에 있다. 민호는 점 A(Ax, Ay)에서 점 B(Bx, By)를 향해 걸어가고 있고, 강호는 점 C(Cx, Cy)에서 점 D(Dx, Dy)를 향해 걸어가고 있다. 민호와 강호는 동시에 출발하고, 민호가 점 B에 도착하는 순간 강호도 점 D에 도착한다. 또, 두 사람은 항상 일정한 속도로 걸어간다. 두 사람의 거리가 가장 가까울 때, 거리를 구하는 프로그램을 작성하시오.

두 점 (x1, y1), (x2, y2)사이의 거리는 (x2−x1)2+(y2−y1)2\(\sqrt{(x2-x1)^2 + (y2-y1)^2}\) 이다.

입력

첫째 줄에 Ax, Ay, Bx, By, Cx, Cy, Dx, Dy가 주어진다. 입력으로 주어지는 모든 좌표는 0보다 크거나 같고, 10000보다 작거나 같은 정수이다.

출력

민호와 강호가 가장 가까웠을 때의 거리를 출력한다. 절대/상대 오차는 10-6까지 허용한다.

예제 입력 1

0 0 1 1 2 2 3 3

예제 출력 1

2.8284271247

예제 입력 2

0 0 1 1 1 0 0 1

예제 출력 2

0.0000000000

예제 입력 3

0 0 10 20 30 0 5 10

예제 출력 3

8.2416338387

예제 입력 4

5 5 10 10 7 2 20 30

예제 출력 4

2.8745554697

 

소스코드

ax, ay, bx, by, cx, cy, dx, dy = list(map(int, input().split()))

def dinstance(m):
    m_x = ax * m + bx * (1 - m)
    m_y = ay * m + by * (1 - m)
    k_x = cx * m + dx * (1 - m)
    k_y = cy * m + dy * (1 - m)
    return ((m_x - k_x) ** 2 + (m_y - k_y) ** 2) ** 0.5

start, end = 0, 1
while abs(end - start) > 1e-9:
    one = (start * 2 + end) / 3
    two = (start + end * 2) / 3
    if dinstance(one) > dinstance(two):
        start = one
    else:
        end = two

print('%.16f'%dinstance(start))

'삼분 탐색'을 이용해야 하는 문제였습니다.

 

삼분 탐색

1. 시작점에서 끝점까지의 거리를 삼등분합니다.

    1-1. 첫번째 분할 지점 : one = (start * 2 + end) / 3

    1-2. 두번째 분할 지점 : two = (start + end * 2) / 3

2. 거리를 구하는 함수를 dist라고 할 때

    2-1. dist(one) > dist(two) : 거리가 최소가 되는 값이 뒤쪽에 있으므로 start = one

    2-2. dist(one) < dist(two) : 거리가 최소가 되는 값이 앞쪽에 있으므로 end = two

3. 오차 범위 내에서 구한 최종 거리를 구합니다.

 

 

출처 : https://goodsosbva.tistory.com/m/37?category=454008