Programming Problem #25
"Deep Space Patrol"

You are the captain of a small faster-than-light patrol ship, and your job is to patrol the perimeters of small planetary clusters in the spiral arm of the Milky Way galaxy. When you are assigned to a cluster, you are given (X,Y) coordinates for every planet. (Since the planets lie on roughly the same plane, no Z coordinate is needed.) You must calculate a perimeter tour, which is a sequence of planets of minimal length that, when visited in order, will completely encircle the cluster. In other words, if you connected all of the planets in the tour with straight lines to form a polygon, all of the planets not in the tour would lie within the polygon.

The input consists of one or more clusters. Each cluster is in the following format:

  1. Number of planets in the cluster. The value -1 signals the end of the input.
  2. The X and Y coordinates for each planet, one planet per line. The coordinates are real numbers, left-justified and separated by exactly one space.
For each input cluster the output must be as follows.
  1. The heading Cluster #N left-justified on a line by itself.
  2. The numbers of the planets in the tour, one per line. (Planet 1 is the one whose coordinates were listed first, etc.) The first planet listed must be the one with the smallest Y coordinate (ties can be broken arbitrarily), and the remaining planets must be listed by following the tour counter-clockwise.
Input must be read from the file "prob25.in", and output must be written to the file "prob25.out". All output to the screen will be ignored.

Example Input

<BOF>
7
1.334 -2.001
-2.5642 3.0
1.788 1.788
-2.901 -4.6
5.0 1.0
3.99 -5.1441
-0.003 0.098
-1
<EOF>

Example Output

Cluster #1
6
5
2
4
Dr. Eric Shade