Many science fiction stories take place on distant planets in galaxies far, far,
away. Some of the best writers will spend time researching the relevant
scientific fields of today to make their futuristic technology seem believable
to a modern day audience. As a budding young writer participating in the
National Novel Writing Month (NaNoWriMo) in November, you'd like to do some
technological research as well to make sure your own SF universe is up to
par.
In your own SF novel, humanity has spread out throughout the galaxy
and has come to colonize many a planet. Aside from the obvious requirement of
interstellar space flight in your book, you'd like to keep all other
technologies, computers especially, similar to what is available in today's
world. That means the computer networks on many of the colonized planets will still be
designed by running copper or fiber optic cable between the computers.
Modern computer networks use packet switching which means that you do not
have to physically run a separate cable between every pair of computers. It's
enough that the computer network remains strongly connected. In other
words, it's enough that for every pair of computers on the network, some path
exists such that packets traveling to and fro between the computers can reach
their destinations by being forwarded through any number of computers in-between.
This property of packet switching allows us to minimize how much cable has to be
laid down to allow every computer on the network to communicate with every
other. As a budding SF writer, you'd like to know the absolute minimum total
length of cable that would be required to create a computer network between all
the cities on your newly colonized planet, assuming there are no redundant or
aggregate links in the network. When performing your calculations,
you may assume that the planet is a perfect sphere, all the cables are run along
the surface of the planet, and that no surface obstructions (like rivers or
mountain ranges) exist to impede the run of cable.
The input to this problem will specify the diameter of the planet in question,
and it will include a list of city coordinates given in degrees of
latitude and longitude. For those who are not as cartographically
savvy as they'd like, latitude is an angular measurement ranging from
−90° at the South pole to +90° at the North pole and with 0°
located at a planet's equator. Longitude is an angular measurement
ranging between −180° and +180° with 0° specifying the
prime meridian. By convention negative longitude represents locations to
the West of the prime meridian, and positive longitude presents locations to the
East.
Input to this problem will begin with a line containing a single integer
N (1 ≤ N ≤ 100) indicating the number of data sets.
Each data set consists of the following components:
For each data set in the input, print a single line. Print either
"IS POSSIBLE" if the available length of cable L is enough to
network all the cities, or print "IS NOT POSSIBLE" if the available
length of cable L is too short.
2 12742 5900 3 51.3 0 42.5 -75 48.8 3 12742 620 2 30.266 97.75 30.45 91.1333
IS POSSIBLE IS NOT POSSIBLE
Migrated from old NTUJ.
2008 South Central USA
| No. | Testdata Range | Score |
|---|