Search
Duplicate

선분과 점

주차
22
문제번호
11664
언어
Python
티어
실버
유형
이분탐색
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

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
복사