0077. Teleporting Lines

Input file name:	lines.in
Output file name:	lines.out
Time limit:	1 s
Memory limit:	64 megabytes

There are n straight lines in the 3d-space. If the space shuttle finds itself on one of them, it can instantly teleport to any other point of this line. Find the minimum amount of time required for the space shuttle to travel from one point in the space to another.

You may assume that the shuttle has constant velocity of 1.

Input file

First line of the input file is filled by an integer number n limited to a maximum value of 100. The next two lines contain 3 coordinates each (x_i, y_i, z_i) and describe starting and ending point of the shuttle travelling. The rest of file consists of n lines each describing i-th straight line by specifying two different points on it, so they all will contain 6 numbers (x_{i, 1}, y_{i, 1}, z_{i, 1}, x_{i, 2}, y_{i, 2}, z_{i, 2}).

You may assume that the first and the second points describing each line are different.

A single teleport line may be described in the input file more than once.

Output file

You are to display only one number – the minimum amount of time required. The output should be rounded up to 6 digits after decimal point.

Examples:

lines.in	lines.out
2 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 1	1.000000

Source: Petrozavodsk Winter 2003. Our Special Contest on Geometry, Wednesday, February 05
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version