Trick or Treat#1251
Johnny and his friends decided to spend Halloween night collecting candy from the houses in their village. Since the village is too large for a single group to collect candy from all the houses in sequence, they decided to split up, so that each of them would go to a different house, collect candy there (or wreak havoc if the residents do not give out candy), and return to a meeting point arranged in advance.
There are houses in the village, whose positions can be identified by their Cartesian coordinates on the Euclidean plane. Johnny's group also consists of people (including Johnny himself). They decided to distribute the candy after everyone returned with their loot. The houses may be far apart, but Johnny wants to eat the candy as soon as possible.
Considering that, due to the reaction of some villagers to their hospitality, the local authorities may be searching for some of the children, they 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 houses may be floating houses (y = 0). Each child's walking speed is meter per second, and they can move in any direction on the plane.
At exactly midnight, each child will knock on the door of the house they have chosen, instantly collect the candy, and return to the meeting point along the shortest route. Tell Johnny at what time he will be able to start eating the candy.
Each test case starts with a line containing the number of houses (1 \leq n \leq 50000). The next lines describe the positions of the houses; each line contains two real numbers and (-200\ 000 \leq x, y \leq 200\ 000) — the coordinates of the house in meters. All houses are at different locations. Each test case is followed by a blank line. A line with n = 0 marks the end of the input and should not be processed.
For each test case, print two numbers in a line: the -coordinate of the meeting point on the line y = 0 that minimizes the time of arrival of the last child, and the time itself (measured in seconds after midnight). Print the numbers with decimal digits.
Example 1