Description
Fly Monkey is a well-known program of the circus, which is performed by the beautiful and lovely monkey Pipi. In the program of Fly Monkey, there are two long steel wires in air. Pipi is initially located on one of the wires, and her objective is reaching another wire. Pipi must first crawl over the wire from her initial position by some distance, and then jump to some position of another wire. Since Pipi moves quite fast, the trace of her jumping can be considered as a straight line. To prevent from dangers, Pipi tends to shorten her jumping distance, while cannot crawl by more than distance d in advance to save the time. In this conditions, how long Pipi must jump at least?
Input
Input contains multiple test cases. Each test case contains 16 real numbers in one line, which are x1, y1, z1, x2, y2, z2, x3, y3, z3, x4, y4, z4, xp, yp, zp, d. (x1, y1, z1)–(x2, y2, z2) are the coordinates of the two ends of the first wire, (x3, y3, z3)–(x4, y4, z4) are the coordinates of the two ends of the second wire, (xp, yp, zp) is the coordinate of the initial position of Pipi, d is the maximum distance Pipi can crawl. It is guaranteed that Pipi must locate on the first wire, and the lengths of the two wires are positive. But wires may intersect or even overlap.
Output
There is only one line for each test case, which contains a real number. Three digits after decimal point are preserved by rounding.
Sample Input
0.0 0.0 0.0 4.0 4.0 0.0 4.0 0.0 1.0 0.0 4.0 1.0 2.0 2.0 0.0 10.0
Sample Output
1.000
http://poj.org/problem?id=2913
