Supply Mission#2760
You are to fly a helicopter to bring supplies to a number of submarines that are currently moving across the ocean. The coordinates of the helicopter base and each submarine, as well as the velocity of each submarine and the helicopter, are provided. Each submarine travels constantly at a heading and speed specified by the velocity vector (vx, vy), which means that after hour it would have traveled km in the direction and km in the direction ( and may be negative). The length of this vector determines the speed. The helicopter is capable of flying at a constant speed in any direction (assume that acceleration and deceleration are instantaneous).
The helicopter must land on each submarine at least once, and it takes hour at each stop to unload supplies and refuel. Each submarine will rise to the surface at the appropriate landing time and submerge as soon as the helicopter leaves. The velocity of each submarine is not affected by any change in depth. The helicopter can carry enough supplies for all submarines without returning to the base. All coordinates are given in kilometers, all velocities and speeds in kilometers per hour. You may assume the helicopter travels at a greater speed than every submarine. Note that the submarines' paths may cross each other or the helicopter base, but since they can adjust their depth, there will be no collisions.
Find the shortest time for the helicopter to bring supplies to each submarine from the base and return to its base.
The input consists of several cases. Each case starts with a line containing an integer (1 \leq N \leq 8), the number of submarines. The next lines each contain integers: the initial coordinates of the -th submarine and its velocity vector. The last line of each case contains integers representing the coordinates of the helicopter base and the speed of the helicopter. The end of input is indicated by a case that starts with N = 0; this case should not be processed. All input integers have absolute value at most .
For each case, print its case number, a colon, then the minimum amount of time required to complete the mission in the following format:
Case a: b hour(s) c minute(s) d second(s)
where , , , are appropriate non-negative integers, and and are at most . The time should be rounded up to the next second.
Example 1