2 shunfurh shunfurh 于 2017.08.31 16:44 提问

Reforestation

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

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.15 23:45
已采纳
Csdn user default icon
上传中...
上传图片
插入图片