0077. Teleporting Lines

Имя входного файла:	lines.in
Имя выходного файла:	lines.out
Ограничение по времени:	1 s
Ограничение по памяти:	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

Источник: Petrozavodsk Winter 2003. Our Special Contest on Geometry, Wednesday, February 05
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати