|
D |
Dumb Eucelics' Pyramid Walk |
Little ant Eucelics has been given a holy task. He
is to walk from anthill Almapores to another anthill Bigopores, all on his own,
unguided by any other ant through a flat desert terrain under the scorching
heat of the sun. As if that was not enough, there is a huge pyramid structure
standing on the ground, which might force him to take a longer route. He has
therefore asked you to calculate the shortest possible distance that he must
travel in order to reach his goal, walking around or over the pyramid if
necessary.
The pyramid has a square base on the ground. For
this problem we will use a Cartesian coordinate system with its origin on the
ground at the exact center of the base of the pyramid, while axes are drawn
such that the corners of the base square are at coordinates (-10,-10),
(-10,10), (10,10) and (10,-10).
Input
The
input consists of multiple test cases. The first line of the input is an
integer T (≤150), the
number of test cases. This line is followed by T more lines, each specifying a single test case. Each of
these lines specify five space-separated real numbers are in the format “Ax Ay Bx By
h”, each with at most two digits after the decimal point. The
location of Almapores and Bigopores are given by (Ax, Ay)
and (Bx, By) respectively. The
height of the pyramid is given by h.
All lengths are measured in meters. You may assume that the two anthills at
distinct locations, and none of the two anthills lie inside the pyramid. The
inputs will be such that |Ax|, |Ay|, |Bx|,
|By|≤25, 0≤h≤150.
Output
You must produce a single line of output for each input test case. Each line should be of the format “Case c: d”, where c is the serial number of the case starting from 1, and d is the shortest walking distance as asked for in the problem. Your answer will be accepted if absolute error of your output is less than 10-6.
|
Sample Input |
Sample Output |
|
3 -13 0 13 0 50 -13 0 13 0 70 -13 0 13 0 100 |
Case
1: 40.78474941 Case
2: 40.88061302 Case 3: 40.88061302 |
Problemsetter: Samee Zahur, Special Thanks: Jane Alam Jan