11664번: 선분과 점

Memo

로직 설명

• 점 A와 점 B의 x,y,z 값 각각을 left, right로 두고 중간값을 만듭니다. 그 중간값은 선분 AB위에 있습니다.
• 바로 위에서 구한 점과 점 A, 점 C를 꼭지점으로 하는 삼각형을 만듭니다.
• 해당 삼각형이 둔각이라면, 선분 AB 위의 점이 B와 조금 더 가깝게 이동해야 직각이 되므로 (직각이 되어야 최소 값이 되므로) left를 mid 값으로 바꿔줍니다.
• 반대로, 예각이라면 A와 좀 더 가까워야 직각이 되므로 right값을 mid값으로 바꿔줍니다.

어려웠던 부분 😭

• 3차원 공간에서 이분탐색을 통해 답을 도출해본 적이 처음이라 .. 아이디어를 생각해 내기가 어려웠습니다.
• 절대/상대 오차에 대한 고려가 쉽지 않았습니다.

Code

제출 날짜

2021/06/07

import sys

Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz = map(int, sys.stdin.readline().split())

def cal_triangle(x, y, z):
    a = (x - Cx) ** 2 + (y - Cy) ** 2 + (z - Cz) ** 2
    b = (x - Ax) ** 2 + (y - Ay) ** 2 + (z - Az) ** 2
    c = (Cx - Ax) ** 2 + (Cy - Ay) ** 2 + (Cz - Az) ** 2
    if (a + b > c):
        return -1
    elif (a + b == c):
        return 0
    else:
        return 1

left_x = Ax
left_y = Ay
left_z = Az

right_x = Bx
right_y = By
right_z = Bz

while (True):
    mid_x = (left_x + right_x) / 2
    mid_y = (left_y + right_y) / 2
    mid_z = (left_z + right_z) / 2
    if (abs(left_x - right_x) < 0.00000000001 and abs(left_y - right_y) < 0.00000000001 and abs(left_z - right_z) < 0.00000000001):
        break
    val = cal_triangle(mid_x, mid_y, mid_z)
    if (val == 0):
        right_x = mid_x
        right_y = mid_y
        right_z = mid_z
        break
    if (val > 0): #둔각
        left_x = mid_x
        left_y = mid_y
        left_z = mid_z
    else:
        right_x = mid_x
        right_y = mid_y
        right_z = mid_z
print('%0.10f'%((Cx - right_x) ** 2 + (Cy - right_y) ** 2 + (Cz - right_z) ** 2)**(0.5))