Memo
로직 설명
•
점 A와 점 B의 x,y,z 값 각각을 left, right로 두고 중간값을 만듭니다. 그 중간값은 선분 AB위에 있습니다.
•
바로 위에서 구한 점과 점 A, 점 C를 꼭지점으로 하는 삼각형을 만듭니다.
•
해당 삼각형이 둔각이라면, 선분 AB 위의 점이 B와 조금 더 가깝게 이동해야 직각이 되므로 (직각이 되어야 최소 값이 되므로) left를 mid 값으로 바꿔줍니다.
•
반대로, 예각이라면 A와 좀 더 가까워야 직각이 되므로 right값을 mid값으로 바꿔줍니다.
어려웠던 부분
•
3차원 공간에서 이분탐색을 통해 답을 도출해본 적이 처음이라 .. 아이디어를 생각해 내기가 어려웠습니다.
•
절대/상대 오차에 대한 고려가 쉽지 않았습니다.
Code
제출 날짜
@6/7/2021
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))
Python
복사