Problem 5: Communication Planning for Phobos
Life
has been found on Phobos, one of the satellites of Mars! Unfortunately, the life forms there arent
quite as advanced as those on Earth, and they dont have modern communications
(at least by Earth standards). The
Advanced Communication Management Company (ACM) has decided to build a central
office and connect the Phobosians homes for communication (telephone,
television, Internet, and so forth).
They naturally want to minimize their capital outlay in this effort, and
they need to decide how to lay fiber optic cable (essentially on the surface)
so the smallest amount is used. Since
ACM uses digital broadband technology, it is only necessary that there be a
cable path that connects every subscriber and the central office. That is, there does not necessarily need to
be a separate cable from the central office to each subscribers home.
We know the precise location of each
Phobosians home and the planned ACM central office on the surface. These are given using longitude and
latitude. Longitude is measured from an
arbitrary meridian on the surface of Phobos, and has values in the range -180 degrees to +180 degrees. Latitude is measured from the equator, and
has values in the range -90 degrees to
+90 degrees. For planning purposes we
assume Phobos is perfectly spherical, exactly 16.7 miles in diameter. The figure to the left illustrates one
possible location (+800 longitude,
+300 latitude).
INPUT
There
will be one or more sets of input data.
Each set will contain, in order, an integer N no larger than 100,
but at least 2, followed by N pairs of real numbers, each pair giving
the unique longitude and latitude, in degrees, of a Phobosians home or the
central office. A single integer zero
will follow the last data set.
OUTPUT
For
each input data set print a single line containing the data set number (1, 2,
) and the number of miles of cable required to connect all the Phobosians
homes and the central office; show two fractional digits in the distance.