eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ritual Circle

Ritual Circle

Zaman məhdudiyyəti 60 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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.

Giriş verilənləri

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.

Çıxış verilənləri

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 , 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 in nitesimally small distance away from (1/2, 1/2) in a direction toward the point (0, 1), with a radius that is in nitesimally larger than .

The fourth example is a degenerate case with only one companion, in which case a circle of zero radius works.

Nümunə

Giriş verilənləri #1
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
Çıxış verilənləri #1
The Orcs are close
0.707106781186548
0.707106781186548
0