Space trip
Problem
In the MMORPG "Space Traders Online" the speed of the player's movement between the stars is limited to one parsec per second. At this speed, you can quickly get to the nearest stars, but it can take several hours to travel from one end of the galaxy to the other. To speed up such long journeys, the creators of the game made several "wormholes" — tunnels connecting two points in space, which allow you to instantly move back and forth between these points.
Write a program that calculates the minimum travel time using wormhole information.
The first input line contains an integer N (1 ≤ N ≤ 100). This is followed by a line containing 6 integers — coordinates of start (xs,ys,zs) and end (xt,y t,zt) travel points. This is followed by N lines containing 6 integers — coordinates of the ends of "wormholes". All coordinates are measured in parsecs and are in the range from 0 to 10000, and there are no points with the same coordinates.
Print the minimum travel time in seconds with a precision of at least 10
−6.
Examples
| # |
Input |
Output |
| 1 |
1
0 0 0 100 100 0
1 1 1 50 100 10
|
52.722246 |