/* Problem 5--Communication Planning for Phobos
   Technically speaking, the answers here are incorrect.  The problem
   should have made it clear that no extra nodes were to be added.
   Sometimes you can minimize the total pipeline by adding some extra
   nodes, but this is a MUCH harder problem.  To do this problem, you
   needed to know two things:  how to compute great circle distances
   and how to build a minimum spanning tree. */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PI 3.1415926535897932384626433832795
#define D 16.7
#define R (D/2)

typedef struct coord {  /* hold the spherical coordinates */

 double lon, lat;
} coord;

typedef struct infot { /* stores a location index and the shortest */
                       /* known distance to it */
 double s;
 int i;
} infot;

int main (int argc, char **argv);
double Process (coord *A, int sz);
double GCDist (coord a, coord b);
int min (infot *s, int sz);
double mind (double a, double b);

int main (int argc, char **argv) {

  FILE *in, *out;
  int r, sz, i, cs;
  coord *A;

 in = fopen ("prob5.in","r");
 out = fopen ("prob5.out","w");
 cs = 0;
 for (;;) {
  fscanf (in,"%d",&sz); /* read in number of points */
 if (sz==0) break;
  A = malloc (sz*sizeof (coord));
  i = 0;
  for (;;) {
  if (i==sz) break; /* read in points and convert to radians */
   fscanf (in,"%lf %lf",&A[i].lon,&A[i].lat);
   A[i].lon *= PI/180;
   A[i].lat *= PI/180;
   i++;
  }
  fprintf (out,"Case %d: %.2f miles\n",++cs,Process (A,sz));
  free (A);
 }
 fclose (in);
 fclose (out);
 r = EXIT_SUCCESS;
 return r;
}

/* Process takes an array of coordinates A of size sz and returns the
   minimum amount of pipeline needed to connect all of them.  This
   uses Prim's algorithm to find the minimum spanning tree. */
double Process (coord *A, int sz) {

  double d;
  int i, p, t;
  infot *s;

 d = 0;
 s = malloc ((sz-1)*sizeof (infot));
 i = 0;
 for (;;) { /* find the distance from the first point to all the */
 if (i==sz-1) break; /* others */
  s[i].s = GCDist (A[0],A[i+1]);
  s[i].i = i+1;
  i++;
 }
 sz--;
 for (;;) { /* At each step we find the closest point to the ones */
 if (sz==0) break; /* already in the tree.  We add it to the tree */
  p = min (s,sz);  /* and update the distances. */
  t = s[p].i;
  d += s[p].s;
  sz--;
  s[p] = s[sz];
  i = 0;
  for (;;) {
  if (i==sz) break;
   s[i].s = mind (s[i].s,GCDist(A[t],A[s[i].i]));
   i++;
  }
 }
 free (s);
 return d;
}

/* GCDist returns the great circle distance between coordinates a and
   b */
double GCDist (coord a, coord b) {

  double d;

 d = R*acos (cos(a.lat)*cos(b.lat)*
             cos(a.lon-b.lon)+sin(a.lat)*sin(b.lat));
 return d;
}

/* min returns the position of the smallest distance in array s of size
   sz. */
int min (infot *s, int sz) {

  int pos, i;

 pos = 0;
 i = 1;
 for (;;) {
 if (i==sz) break;
  if (s[i].s < s[pos].s) {
   pos = i;
  } else {
  }
  i++;
 }
 return pos;
}

/* mind returns the smaller of two floating-point numbers a and b. */
double mind (double a, double b) {

  double m;

 if (a < b) {
  m = a;
 } else {
  m = b;
 }
 return m;
}