Segment and Point

Interview

Time limit1sMemory limit256 MB

Summary

Find the closest point on segment AB to point C in 3D and print the distance with ten decimals.

Level: Easy3 of 10
Topics: Geometry, Math
Solved: No attempts yet

Problem

A segment and a point lie in three dimensional space. The endpoints of the segment are $A(A_x, A_y, A_z)$ and $B(B_x, B_y, B_z)$ , and the point is $C(C_x, C_y, C_z)$ .

Write a program that finds the point of the segment closest to $C$ and reports that distance. This value is the minimum distance between the segment and the point.

The distance between $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2)$ is $\sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2}$ .

$A$ and $B$ may be the same point. The segment is then a single point.

Input

The first line contains nine integers $A_x$ , $A_y$ , $A_z$ , $B_x$ , $B_y$ , $B_z$ , $C_x$ , $C_y$ , $C_z$ separated by spaces. Every coordinate is an integer between 0 and 10000, inclusive.

Output

On the first line, print the minimum distance between the segment and the point, rounded to ten digits after the decimal point. Print exactly ten digits after the decimal point whatever the value is. For example, an answer of zero is printed as 0.0000000000.

Examples6

Example 1
Input
```
0 0 0 1 1 1 2 2 2
```
Expected output
```
1.7320508076
```
Example 2
Input
```
0 0 0 10 10 10 5 5 5
```
Expected output
```
0.0000000000
```

Example 3

Input

10 20 30 40 50 60 45 35 25

Expected output

28.2842712475

Example 4
Input
```
0 0 0 1 1 1 0 0 1
```
Expected output
```
0.8164965809
```
Example 5
Input
```
0 0 0 1 0 1 0 1 0
```
Expected output
```
1.0000000000
```
Example 6
Input
```
0 0 0 1 1 1 7 6 5
```
Expected output
```
8.7749643874
```