Trick or Treat |
There are n houses in the village, the positions of which can be identified with their Cartesian coordinates on the Euclidean plane. Johnny's gang is also made up of n people (including Johnny himself). They have decided to distribute the candy after everybody comes back with their booty. The houses might be far away, but Johnny's interest is in eating the candy as soon as possible.
Keeping in mind that, because of their response to the hospitality of some villagers, some children might be wanted by the local authorities, they have agreed to fix the meeting point by the river running through the village, which is the line y = 0. Note that there may be houses on both sides of the river, and some of the houses may be houseboats (y = 0). The walking speed of every child is 1 meter per second, and they can move along any direction on the plane.
At exactly midnight, each child will knock on the door of the house he has chosen, collect the candy instantaneously, and walk back along the shortest route to the meeting point. Tell Johnny at what time he will be able to start eating the candy.
A blank line follows each case. A line with n = 0 indicates the end of the input; do not write any output for this case.
2 1.5 1.5 3 0 1 0 0 4 1 4 4 4 -3 3 2 4 5 4 7 -4 0 7 -6 -2 4 8 -5 0
1.500000000 1.500000000 0.000000000 0.000000000 1.000000000 5.000000000 3.136363636 7.136363636