2008 Canadian Computing Competition, Day 2

Day 2, Problem 3: 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

\frac{R}{1+10^{-4}} < a < R(1+10^{-4})

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.

Sample Input

4
1 1
1 -1
-1 -1
-1 1

Sample Output

1.41421356
A circle centered at the origin with radius sqrt(2).

Grading

You may assume that 25% of the test cases will have at most 50 trees. You may assume that 95% of the test cases will have at most 1000 trees. All test cases will have at most 100 000 trees. Your solution must use at most 512MB of memory and run in at most 5 seconds.

All Submissions
Best Solutions


Point Value: 50 (partial)
Time Limit: 1.00s
Memory Limit: 512M
Added: Apr 25, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Why the f*ck is this only 50? This question is impractical to fully solve. I've still yet to find a couple days to try it out.

It's not impractical, just that you can't code. I have seen your submissions.

Very difficult, yes, but not impossible, and what do you mean by "only" 50

This question is soooooo easy

Can't anyone here find an actual hard problem. I'm getting bored. This site is stupid someone kick me out.

Who are you? Do you go to Woburn?

/*
Who am I? A <HACKER>! Don't worry about me. It's all good as long as I know about you!
*/
getRecked = true;
while (getRecked):
self.Hack();

Says the one who submitted third-party library code to "Landing"...

Says the guy that copied my answer. That's right, I know, I checked!

Seems like you're getting humoured by the others, but I'll gladly help kick you out.

kill = true;
while (kill):
self.kill_jargon();
self.hack_wcipeg();

this guy is the dumbest kid... just using a bit a coding idea to make themself look cool... a real coder never needs to force anything to look cool. We are who we are.