So, here is the problem:
You have N circles on a plane, with (4 <= N <= 50000). For each circle, you have the coordinates of the center and the radius (all of them are specified with floating-point numbers). You have to output the radius of the largest circle you can put inside the rectangle formed by the center of the first 4 circles of input, such that this circle doesn't touch any of the other ones given circles nor is inside of any of the other given circles.
Constraints: - no circle intersect another circle on input. - no circle is inside another circle on input. - no circle has radius <= 0. - no two centers of the given circles coincide. - the output radius should have precision 10^-6.
That's it! I would really appreciate some hint.
You have to use binary search by the answer. So you need to increase the radius of each circle at the checked value and determine "Whether there is any point which is located out of all circles?". It can be solved by using the divide and conquer algorithm. If all the circles don't intersect current rectangle, then we've already found uncovered points. If some circles intersect our rectangle, then we need to devide our rectangle into 4 smaller and return to the first part of algorithm. Otherwise, if the current rectangle is entirely inside any circle, then we exit from current branch of recursion. It works O(N * log(MaxAns/eps)).. But I'm not sure in this asymptotic.
Thanks for answering. Could you elaborate a bit more what do you check in the binary search? That is, what do you mean by "increase the radius of each circle at the checked value"?
We need to be able to check: is it possible to place a circle of radius R. This problem is equivalent to search uncovered point inside the rectangle, after increasing the radius of the circles on R. Also you have to remember to reduce the sides of the rectangle on R.
so you transform the problem in:
Search for the largest dR we can increase the radius of every input circle such that there is at least one point outside of every input circle and inside the above mentioned rectangle, and the output would be this dR?
Is this correct?
Yes, but not "_the above mentioned rectangle_", because you have to decrease the sides of it.
mmm....then, what would output your algorithm in this case?
image
The answer is a circle with the same radius that circles 5 and 8 of input, but if you increase by that radius the other circles, and decrease by that radius the sides of the rectangle, the later will be completely covered by the input circles. Is this correct?
If we do what you say by the R = 2-eps, everythin will be OK:) Because it'll be uncovered point in a center of rectangle.
UPD: And if we don't reduce the sides of rectangle (but increase the radius of all circles by 2), it would means that the point with coordinate (4; 1.9) is a center of result circle. But it's false. Because it intersects with bottom side of rectangle.
When you test whether it's possible that the answer is R, you temporarily increase radius of every circle by R (imagine a circle from the point we search for, it has radius R, so instead of checking whether two circles coincide (one of radius R and the second being the one of the given circles from the statement), we can just check, whether the point lies one of the given circles with increased radius.