MAXRAD - Maximum Radius

no tags 

Maximum Radius | MAXRAD

Time Limit: 2 seconds

You will be given some 2D points. You need to draw circles with each point considering as a center of a circle with minimum radius 1. And no two drawn circles should intersect with each other or contain each other. Now you have to find the maximum radius any circle can have so that all the circles have radius greater or equal to 1 and no two circles intersect with each other or contain each other. You have to print the maximum radius. If it is not possible to maintain the restriction for any radius, then you should print -1.000000.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a line containing an integer N (2 ≤ N ≤ 1000) denoting the number of 2D points. Each of the next N lines contains two integers xi yi (-104 ≤ xi, yi ≤ 104) denoting the co-ordinate of a point. These points may not be distinct.

Output

For each case, print the maximum radius a circle can have. If it is not possible to maintain the restriction then you should print -1.000000. Errors less than 10-6 will be ignored.

Sample Input

Output for Sample Input

2

2

1 1

3 1

2

1 1

2 1

1.000000

-1.000000

 

Problem Setter: Ahmad Faiyaz

Special Thanks: Aninda Majumder


hide comments
:.Mohib.:: 2015-02-27 12:58:34

feeling awsm after AC.... :)...44th...

RIVU DAS: 2014-05-21 18:02:08

C -> TLE
C++ -> AC!!

The Alchemist: 2014-02-15 22:25:34

studied a lot of maths for this finally AC :D


Added by:Faiyaz
Date:2013-12-24
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64