Wally World#2683
Two star-crossed lovers want to meet. The lovers are located at distinct points in the plane (but then again, aren't we all?). They can move freely except for a single wall that cannot be crossed. The wall is a line segment, parallel to either the or axis. Each lover can move unit per second. What is the minimal time it will take them to meet if both choose the best path?
The input for each test case consists of two lines, each containing four integers. The first two integers specify the and coordinates of the first lover; the next two specify the and coordinates of the second lover. The next four integers specify the start and end points of the wall. In all cases, neither lover will be on the (infinite) line containing the wall—that is, the wall extended in both directions. All coordinates are positive and not greater than , and neither lover starts on the wall.
The input is terminated by a line containing four zeroes.
For each test case, output the minimum meeting time in seconds, printed to exactly decimal places, using the output format shown in the example.
Example 1