LANDING - Landing

Keep watching the skies! Alien spacecraft are due to land any day now to share all of their advanced programming secrets with us.

In preparation for this day, you've been asked with preparing a landing pad for our visitors in a given field. Unfortunately, due to environmental considerations, you will not be permitted to remove any of the trees which currently exist on the field. These trees are of immense scientific research, since they have zero radius and only grow at points with integer co-ordinates. However, this could be a blessing in disguise. For security reasons, the landing pad must be in contact with at least three trees. Security cameras will be placed at the tops of these trees.

Alien spacecraft are perfectly circular craft of various sizes, so the landing pad will also be circular. Since it would be polite to warn potential visitors ahead of time if their spacecraft is too large for our landing pad, you must now determine the size of largest circular region that we can place on the field which contacts at least three trees, but does not contain any trees within.

Input

The first line of input consists of the number n of trees (3 ≤ n ≤ 100 000). The next n lines will each consist of a pair of integers x and y (-10000 ≤ x, y ≤ 10000), separated by a space, giving the co-ordinates of a tree. You may assume that no two trees are at the same co-ordinates.

Output

Output the radius of the largest possible landing pad. If the correct answer is R, you should output number a such that

The above calculation is used to define an acceptable range or tolerance for the answer you find. You may also assume that r < 109. You may assume there exists at least one landing pad.

Example

Input:
4
1 1
1 -1
-1 -1
-1 1

Output:
1.414214


Added by:JaceTheMindSculptor
Date:2009-04-09
Time limit:1s-2.029s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO OBJC
Resource:Canadian Computing Competition 2008 Stage 2 Day 2 Problem F

hide comments
2018-06-18 11:58:27
@JaceTheMindSculptor Can you please tell me what's wrong in my code?
2010-08-12 09:43:36 :D
The inequalities with 'a' are just to specify the judge error tolerance. Just print 'R'.

Last edit: 2010-08-12 09:43:53
2010-08-11 21:02:01 cegprakash
I found the correct radius R. then i donno how to find a. Can u help me how to find 'a'
2010-08-11 18:27:52 JaceTheMindSculptor
6 digits after decimal point, coordinates are all integers.
2010-08-11 18:27:52 cegprakash
How much digits should be printed after the decimal point?
2010-08-11 18:27:52 cegprakash
co-ordinates of a tree are of integer type or it may be float?
i.e. can a tree exist at (1.5,1.75) ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.