Problem J
Laser-Linked Lighthouses

Photo by Bruce Berrien

After centuries of trying, humankind has finally managed to establish $N$ colonies on Europa. Since they are so far away from the other humans in the Solar System, a bunch of satellite repeaters propagate communications to and from the other colonies.

However, critical nodes in the satellite repeater system and the backup solution has had several hiccups, causing the Europa colonies to be without connection to the outside world for several weeks. Although it now has been fixed, the Europa council has decided that it’s necessary to have a failsafe, and want to construct a bigger and more sensitive satellite dish. However, they can only afford one big satellite dish, so it has to be put near one of the colonies.

That poses another problem: The colonies on Europa currently communicate with each other via the satellite repeater system (yes, the ping is horrendous), and when the system is down, they have to send vehicles instead. To relay the information from the colony with the big satellite dish and in general, they have to set up a communications system between all the colonies. The plan is to set up communication cables eventually, but in the meantime, they have decided to set up a quick and dirty solution: laser lighthouses.

Laser lighthouses are simple things: they can be considered cylinders with an infinitesimally small radius and some height $h$, standing perpendicular to the surface of a planet or moon. As long as the top of a lighthouse has a clear line of sight to the top of another lighthouse, they can directly exchange information. On Europa, that means that the two lighthouses must be high enough that the curvature of Europa’s surface doesn’t interfere with them:

Figure 1: A cut of Europa, where all $4$ lighthouses lie exactly on the cut. The lighthouses in the upper right quadrant are able to communicate because they have a line of sight, whereas the lighthouses in the bottom right quadrant do not.

Fortunately, Europa can be considered a perfect sphere, and its gravity is so weak that spacetime is not warped nearby.

The lighthouses can also communicate indirectly: If lighthouse $i$ wants to send information to lighthouse $j$, it can transmit that information via a sequence of lighthouses with a clear line of sight to each other.

The council has already decided where all the lighthouses’ should be placed, but are unsure how high they have to be. To save costs, they want to prefabricate all lighthouses with the same size, and they want to use the minimum height possible. Can you help them?

Input

The first line contains the integer $N$, the number of laser lighthouses. Then follows $N$ lines, each with two integers $\text {lat}_ i$ and $\text {lon}_ i$, representing the coordinates of the $i$th lighthouse in degrees.

Output

Output the minimum height $h$ the laser lighthouse needs to be, so that any lighthouse $a$ can communicate with any other lighthouse $b$ directly or indirectly. Output the answer in multiples of Europa’s radius.

The output must have a relative or absolute error of at most $10^{-8}$.

Limits

• $2 < N < 1000$

• $-90 \leq \text {lat}_ i \leq 90$ and $-180 < \text {lon}_ i \leq 180$

• $(\text {lat}_ i, \text {lon}_ i) \neq (\text {lat}_ j, \text {lon}_ j)$ for all $i \neq j$

• If $\text {lat}_ i = \pm 90$, then $\text {lon}_ i = 0$

3
90 0
0 -90
0 0

0.41421356237309515

5
60 11
-33 18
38 -122
-38 145
40 116

0.45514138533258275