시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 14 12 1 33.333%

문제

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.

입력

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.

출력

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.

예제 입력

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

예제 출력

The Orcs are close
0.707106781186548
0.707106781186548
0

힌트