MAXRAD - Maximum Radius
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
|
|
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 |