Move Away

This problem asks what point in the intersection of several circles is furthest from the origin.

Solution 1:

The first though in problems like these is interesting points. We could, perhaps, try to take the intersections of any two circles, find the set that define the intersection of all the circles, and then evaluate to find the one furthest from the origin. However, the extreme point may not lie at one of those intersections. Consider even the 1 friend case (poor guy!), there are no intersections to evaluate! We can solve this by also adding the point on each circle which is furthest from the origin. Evaluate all the candidate points for inclusivity and distance, and take the furthest one that is included in the intersection.

Solution 2:

Binary search over the distance from the origin. For a given candidate distance D, evaluate the intersections with any other circle. See if any of those points are in the intersection of all circles. Have to be careful to know if we don't find any such points whether we're too big or too small. Simple to do, just find the furthest and nearest points in the intersection of the neighbors circles. If we're short of that, grow, if we're long, shrink. If we are IN the intersection, grow (since we're finding the furthest point).