Problem K. Knockdown ≡
| Author: | NEERC 2005 | Time limit: | 2 sec | |
| Input file: | knockdown.in | Memory limit: | 64 Mb | |
| Output file: | knockdown.out |
Statement
The Evil Empire is devising a plan to destroy the world. This plan is called "Operation Knockdown". The plan is to place a number of high-yield nuclear bombs in different places around the world, so that their simultaneous detonation will destroy everything on the planet. For the purpose of planning this operation, bombs have destruction distance — the distance from the point of bomb's detonation to all the places where everything is considered destroyed.
Places for the bombs have been already selected. Now the Evil Empire wants to minimize the cost of production for the bombs. It is expensive to design atomic bombs tailored for different destruction distances, so the idea is to design a bomb with a specific destruction distance and to produce bombs according to this design for all the selected places. The problem is to find the minimal required destruction distance for the bomb design, so that destruction of the whole world is ensured.
For this problem the world is modeled as a sphere of a unit radius. The coordinates of the selected points for the bombs are specified in geographic coordinate system with latitude ϕ ( − 90° < ϕ < 90°) and longitude λ ( − 180° < λ ≤ 180°). Latitude is the angle between a point and the equator, and longitude is the angle between a point and the prime meridian. The bombs are never placed on the poles, so their latitude is always less than 90 degrees by its absolute value.
Distances for destruction purposes are measured on the sphere. For example, the distance between the poles is exactly π. The world is considered destroyed if the distance from any point on the sphere to the closest bomb is less or equal to the destruction radius.
Input file format
The first line of the input file contains a single integer number n — the number of the bombs. The following n lines describe the places of the bombs. Each line contains two integer numbers ϕi and λi — latitude and longitude of the bomb. No two bombs are situated in the same place.Output file format
Write to the output file a single number - the minimal destruction radius of the bombs that ensures destruction of the whole world. The answer must be precise up to 10 − 6.Constraints
1 ≤ n ≤ 20, − 90° < ϕ < 90°, − 180° < λ ≤ 180°.Sample tests
| No. | Input file (knockdown.in) |
Output file (knockdown.out) |
|---|---|---|
| 1 | |
|