Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3208
Reforestation

Time Limit: 1 Second      Memory Limit: 32768 KB      Special Judge

The government is making strenuous efforts to reforest the hill. To trace the growing status of the trees, an observer is placed in the middle of the area at the coordinate (0, 0). To simplify our model, let us assume that:
1. the observer has a diameter of 0;
2. the trees have a radius of 0 at the very beginning;
3. all the trees will grow in the same speed until they are stopped for the reasons that if it touches either the observer or another tree.
Let us say that the trees' radius will grow 1 unit length per unit time. So the radius of a tree at the time T would be T if it had not been stopped by then.

What we are interested in here is that when the observer will lose sight on the skyline. Or we put it in the words that the observer could not see anything outside the forest in any horizontal directions.

Input

The first line of the input contains an integer T, T < 150, which is the number of test cases.
In each test case, there is a positive integer N, in the range [1, 200], which is the number of trees. The next N lines each has two integers Xi and Yi indicating the coordinates of the i-th tree. The values of the coordinates are between -10,000 and 10,000 inclusively. All the trees and the observer have different positions.

Output

For each test case, output the time that the observer would lose the sight of the sky. The answer be accurate up to six decimal places. If the observer will never be blocked by the trees, you should output "-1.0" instead.
A relative error of 1e-6 will be accepted.

Sample Input

2
2
0 1
0 -2
3
1 0
0 1
0 -1

Sample Output

2.000000
-1.0

Author: GAO, Fei
Source: The 6th Zhejiang Provincial Collegiate Programming Contest
Submit    Status