Euclid

Interview

Time limit1sMemory limit512 MB

Summary

Given three points in 3D space, find a point minimizing the sum of Euclidean distances to all three.

Level: Medium5 of 10
Topics: Geometry, Math, Implementation, Brute force
Solved: No attempts yet

Problem

Smurfs love to play a computer game called SmurfCraft. The game has a number of power sources to be harvested. Lazy Smurf must build his new base. He has already found the locations of three unoccupied power sources, and now he wants to build his base at a position that minimizes the total distance to all three of those power sources. This problem would not be difficult (even for Lazy Smurf) if the game were not played in 3D. Because Lazy Smurf skipped his geometry classes, he does not know how to solve this problem. Help him.

Input

The input consists of three lines, each containing three integers $x, y, z$ ( $-10^9 \leq x, y, z \leq 10^9$ ), the coordinates of a power source.

Output

Output the minimum possible total distance to all three power sources. Your answer is accepted if the relative or absolute error is less than $10^{-4}$ .

Examples1

Example 1
Input
```
0 0 0
20 0 0
10 20 0
```
Expected output
```
37.320508
```