Ritual Circle
Time Limit: 5 Seconds Memory Limit: 65536 KB
Before the departure of the Fellowship from Rivendell, Bilbo gave Frodo his Elvish-made sword that he called Sting. This sword was special: the blade would glow blue whenever Orcs were close.
Input
The input will contain multiple test cases. Each test case will consist of two sets of points in the plane representing the positions of Frodo's companions and the enemy Orcs, respectively. All of these points will be represented by integer coordinates with component values between 0 and 100 inclusive. Every point in each case will be unique. The total number of points from both sets (Frodo's companions and the Orcs) in any single problem instance will be at most 300, and there will be at most 10 test cases with more than 200 points.
Output
Frodo needs to determine the radius of the smallest circle that contains all of the points of his companions' positions, and excludes all of the points of the Orcs' positions. Whenever such a circle does not exist, then the sword Sting glows blue and Frodo is danger, so print "The Orcs are close". If such a circle does exist, print the radius of the smallest such circle given as a decimal value that is within a relative error of 1e-7.
In the first example, no circle is possible that includes both companions but excludes both Orcs; any such circle would need to have a radius of at least sqrt(1/2), but any circle that large would need to include at least one of the Orcs.
In the third example, a circle may be placed with its center an infinitesimally small distance away from (1/2, 1/2) in a direction toward the point (0, 1), with a radius that is infinitesimally larger than sqrt(1/2).
The fourth example is a degenerate case with only one companion, in which case a circle of zero radius works.
Sample Input
Companions: (0,0) (1,1) Orcs: (1,0) (0,1) Companions: (0,0) (0,1) (1,1) (1,0) Orcs: none Companions: (0,0) (0,1) (1,1) Orcs: (1,0) Companions: (0,0) Orcs: none
Sample Output
The Orcs are close 0.707106781186548 0.707106781186548 0Submit
Source: Pacific Northwest 2012