Place the balloon

I'm unclear as to why, in case 2, the disc with diameter sqrt(2)/2 directly beneath (0,0) doesn't qualify. It is constrained by the set of points and touches none of them.

I don't know what circle with sqrt(2)/2 you are imagining. I agree with the sample output.

I was wrong about the diameter; it can be a full 1.0 in diameter and still be bounded by the convex hull of the points.

That isn't constrained. It can move directly downwards.

ahh... I see now. thank you again.

Can you please double check the test cases for this problem. My brute force checker agrees with my solution on every large test case I have tried, as well as random and hand-chosen small ones. (And submitting the brute force program passes at least the first input file).

Ok, will check this.

Are threads allowed?

If so, would you (the system) sum up their time or determine the time of the main thread of the process only???

Have the test cases been checked? (Just wasn't sure as the other problem was fixed without any mention of it).

Well, instead of checking data-test (which is pointless), I checked your solutions.

Think again. :]

I'm afraid I'm pretty convinced. Perhaps you could try comparing Ashutosh's solution to mine, as from the looks of it he may be experiencing the same problem.

Stephen and Ashutosh can't be wrong at the same time ;)

Might I ask how floating point accuracy is checked?  Basically, which of the following would the following be acceptable output for the first sample input?

1.25

1.250000

1.2500011 (within 10^-6 relative error, but not 10^-6 absolute error)

1.2500001

rejudge in progress.. some explanations later

for those who cudnt make out the problem>>

consider a ground with poles dug all over. find the radius of the fattest man who can stand in this ground :P

Well, at least I now know I wasn't going crazy :) (The scoreboard doesn't seem to be updating with the rejudge by the way.)

Well, I wouldn't doubt in my solution, but I found results are nondeterministic (!).

And bug was in totally easy part of the code - finding maximum in sequence of integers (!).

@Mark Greve, @pieguy. Could you two please submit your accepted solutions again ?

I think everyone who manages to crack this nut should be awarded a PhD!

No, not really...

;-)

Hats off to all those who cracked this nut!!

-1.000000 is acceptable ?

@Balakrishnan - Now you're one of us :D

Now that the contest is over.... Can any one comment on the solution ??

I feel that finding circumcircle of all triangles obtained by delaunay triangulation

(consider only those circle which have points cover more than half of circumference)

and maximising the radius.

Is it correct ?

Yup.

@Tasnim - be careful with cases like

4

0 0

0 1

1 1

1 0

There is a valid answer ( center at .5, .5 ). Your solution might not give that.

@Ajay : My program returns 0.7071068 ..  which is correct ?? Any other cases

@Ajay : My program returns 0.7071068 ..  which is correct ?? Any other cases

Not really :). I mentioned this case only because when you consider each circumcircle, if you just consider only the vertices of that triangle, it would fail for this case. If you find all the points which are closest to the circum center [ a total of 4 points in this case ], then it would work.

admins I would like to know the test case which my program fails (submission id 168306) ?Is it the floating point error or still logical error somewhere ?

@Tasnim: I ran your code and found some small cases it gives a different answer from mine:

2

5

6141 6311

-6233 -3082

4780 -1120

6663 8059

-6259 -3835

5

-1991 -378

9308 -8197

-3569 -6048

8397 7872

-9460 -833

My result:

-1

8408.86046237473

Your result:

8291.7256079

17516.9305787

i used n^2 delauny triangulation. what about others? any one did nlgn?

I did the incremental flip algorithm with random order insertion of vertices which Wikipedia says is O(n log n).  The code is pretty ugly, though.

I did O(n*log(n)).

I used the algorithm mentioned in here:

http://www.geom.uiuc.edu/~samuelp/del_project.html