난이도

Gold 5

인증

문제

3차원 좌표 평면 위에 선분 하나와 점 하나가 있다. 선분의 양 끝점은 A(Ax, Ay, Az)와 B(Bx, By, Bz)로 나타낼 수 있다. 점의 좌표는 C(Cx, Cy, Cz) 이다.

선분과 점 사이의 거리의 최솟값을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 선분과 점의 좌표 Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz가 주어진다. 좌표는 0보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

첫째 줄에 선분과 점 사이의 거리의 최솟값을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

예제 입력

0 0 0 1 1 1 2 2 2

예제 출력

1.7320508076

해설 및 후기

처음엔 간단히 점과 직선 사이 공식을 사용할 수 있겠다고 생각했으나, 선분이라는 점이 걸렸다. 수선의 발이 선분 안에 없다면 점과 직선 사이 공식을 사용할 수 없기 때문이다. 때문에 수선의 발이 선분 안에 존재하는 지를 확인한 후, 있다면 점과 직선 사이 공식을 사용한 최솟값을, 그렇지 않다면 선분의 각 끝 두 점에 대해 최소 거리를 출력한다.

제출 코드

def is_perpendicular_foot_on_segment(A, B, P):
    AB = (B[0] - A[0], B[1] - A[1], B[2] - A[2])
    AP = (P[0] - A[0], P[1] - A[1], P[2] - A[2])
    
    dot_product = AB[0] * AP[0] + AB[1] * AP[1] + AB[2] * AP[2]
    
    squared_length_AB = AB[0]**2 + AB[1]**2 + AB[2]**2
    
    return 0 <= dot_product <= squared_length_AB

x1, y1, z1, x2, y2, z2, x3, y3, z3 = map(int,input().split())
lst = []
pa = [x1-x3, y1-y3, z1-z3]
u = [x2-x1, y2-y1, z2-z1]
uSize = (u[0]**2+u[1]**2+u[2]**2)**0.5
cp = [pa[1]*u[2]-pa[2]*u[1], -(pa[0]*u[2]-pa[2]*u[0]), pa[0]*u[1]-pa[1]*u[0]]
cpSize = (cp[0]**2+cp[1]**2+cp[2]**2)**0.5
d = cpSize/uSize
lst.append(d)
lst.append(((x3-x1)**2+(y3-y1)**2+(z3-z1)**2)**0.5)
lst.append(((x3-x2)**2+(y3-y2)**2+(z3-z2)**2)**0.5)
minX,minY,minZ = min(x1,x2),min(y1,y2),min(z1,z2)
maxX,maxY,maxZ = max(x1,x2),max(y1,y2),max(z1,z2)
if(is_perpendicular_foot_on_segment((x1,y1,z1),(x2,y2,z2),(x3,y3,z3))):
    print(min(lst))
else:
    print(min(lst[1:]))