/* Problem 6--Clustering
   Talk about a poorly worded problem!  This problem is ambiguous in
   two ways.  Although some hints for tie-breaking are given, there are
   still cases in which tie-breaking is not defined.  I chose a way to
   break ties, and this gives me the correct answer, so that's what I'm
   using.  Also, the output format is poorly defined.  In the long line
   in the sample output that needs to be split, one more number could be
   fit on the line if you didn't print the (invisible) trailing space.
   Should trailing spaces be printed?  The specification does not say.
   Anyway, these ambiguities are the only things that make this program
   particularly difficult.  The specification spells out the algorithm;
   all we have to do is code it. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct coord { /* Info pertaining an input point */

 double x, y;
 int gp, id;
} coord;

typedef struct DT { /* Info pertaining to a pair of points */

 double s;
 int i, j, id;
} DT;

int main (int argc, char **argv);
int dcmp (const void *a, const void *b);
void Process (FILE *out, int *cs, coord *C, DT *D, int sz, int dsz);
int match (DT a, DT b);
int ccmp (const void *a, const void *b);
void Print (FILE *out, coord *C, int sz);

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

  FILE *in, *out;
  int r, sz, i, j, k, cs;
  coord *C;
  DT *D;

 in = fopen ("prob6.in","r");
 out = fopen ("prob6.out","w");
 cs = 0;
 for (;;) {
  fscanf (in,"%d",&sz); /* read in case */
 if (sz==0) break;
  C = malloc (sz*sizeof (coord));
  i = 0;
  for (;;) {
  if (i==sz) break;
   fscanf (in,"%lf %lf",&C[i].x,&C[i].y);
   C[i].gp = -1; /* Initialize group membership */
   C[i].id = i;
   i++;
  }
  D = malloc (sz*(sz-1)/2*sizeof (DT));
  i = k = 0; /* Compute and store all distances between all pairs */
  for (;;) {
  if (i==sz-1) break;
   j = i+1;
   for (;;) {
   if (j==sz) break;
    D[k].s = sqrt (pow (C[i].x-C[j].x,2) + pow (C[i].y-C[j].y,2));
    D[k].i = i; /* The identity of the two points in question */
    D[k].j = j;
    D[k].id = k;
    k++;
    j++;
   }
   i++;
  }
  qsort (D,k,sizeof (DT),dcmp); /* sort by distance */
  Process (out,&cs,C,D,sz,k); /* Compute cluster */
  free (D);
  free (C);
 }
 fclose (in);
 fclose (out);
 r = EXIT_SUCCESS;
 return r;
}

/* dcmp compares two DT's.  The smaller one is the one with the smaller
   distance.  In the event of a tie, the smaller is the one that was
   generated first. */
int dcmp (const void *a, const void *b) {

  int c;
  DT *aa, *bb;

 aa = (DT *)a;
 bb = (DT *)b;
 if (aa->s < bb->s) {
  c = -1;
 } else {
  if (aa->s > bb->s) {
   c = 1;
  } else {
   c = aa->id - bb->id;
  }
 }
 return c;
}

/* Process does the bulk of the work adding points to groups based on
   distances to other groups */
void Process (FILE *out, int *cs, coord *C, DT *D, int sz, int dsz) {

  int gps, i, p, j, m, op, oj;

 fprintf (out,"Case %d:\n",++*cs);
 C[D[0].i].gp = C[D[0].j].gp = 0; /* Group 1 */
 i = 1;
 for (;;) { /* Find two other points for Group 2 */
 if (C[D[i].i].gp == -1 && C[D[i].j].gp == -1) break;
  i++;
 }
 C[D[i].i].gp = C[D[i].j].gp = 1; /* Group 2 */
 gps = 2;
 i = 1;
 for (;;) { /* Go through the pairs of points one-by-one */
 if (i==dsz) break; /* Skip if both points are already in groups */
  if (C[D[i].i].gp != -1 && C[D[i].j].gp != -1) {
   i++;
  } else { /* We are putting a new point into a group, but see if */
   p = i;  /* there is a better choice nearby. */
   j = i+1;
   for (;;) {
   if (j==dsz || D[j].s - D[p].s > 0.001) break;
    m = match (D[p],D[j]); /* If a coordinate matches our previous */
    if (m!=-1 && C[m].gp == -1) { /* point, we see if its a better */
     op = D[p].i+D[p].j-m;        /* fit */
     oj = D[j].i+D[j].j-m;
     if ((C[op].gp == -1 && C[oj].gp != -1) ||
         (C[op].gp != -1 && C[oj].gp != -1 && C[oj].gp < C[op].gp)) {
      p = j; /* If the other point's group is better than ours, go */
     } else {/* with the other one. */
     }
    } else {
    }
    j++;
   }
   if (C[D[p].i].gp == -1 && C[D[p].j].gp != -1) {
    C[D[p].i].gp = C[D[p].j].gp; /* Assign point to other group */
   } else {
    if (C[D[p].i].gp != -1 && C[D[p].j].gp == -1) {
     C[D[p].j].gp = C[D[p].i].gp;
    } else {
     C[D[p].i].gp = C[D[p].j].gp = gps; /* Make new group */
     gps++;
    }
   }
  }
 } /* Sort points by group affiliation and print them */
 qsort (C,sz,sizeof (coord),ccmp);
 Print (out,C,sz);
}

/* match looks at DT's a and b to see if they have a point in common.
   If so, it returns that point; otherwise, it returns -1. */
int match (DT a, DT b) {

  int m;

 if (a.i==b.i || a.i==b.j) {
  m = a.i;
 } else {
  if (a.j==b.i || a.j==b.j) {
   m = a.j;
  } else {
   m = -1;
  }
 }
 return m;
}

/* ccmp compares two coords.  The smaller one is the one with the
   smaller group number, or, if they tie, the smaller is the one with
   the smaller point number. */
int ccmp (const void *a, const void *b) {

  int c;
  coord *aa, *bb;

 aa = (coord *)a;
 bb = (coord *)b;
 c = aa->gp - bb->gp;
 if (c==0) {
  c = aa->id - bb->id;
 } else {
 }
 return c;
}

/* Print prints our sorted coordinate way in the manner specified.*/
void Print (FILE *out, coord *C, int sz) {

  int gp, i, j;
  char pstr[500], istr[6], *t;

 gp = -1;
 i = 0;
 for (;;) {
  if (i==sz || C[i].gp != gp) { /* If our group changes or we run out */
   if (gp != -1) {              /* of points, print the previous group*/
    pstr[strlen(pstr)-2]=0;
    t = pstr;
    for (;;) { /* If string too long, find appropriate place to break */
    if (strlen (t) <= 67) break;
     j = 67;
     for (;;) {
     if (t[j]==' ') break;
      j--;
     }
     t[j] = 0;
     fprintf (out,"%s\n",t);
     fprintf (out,"           ");
     t = &t[j+1];
    }
    fprintf (out,"%s\n",t); /* print out last bit of string */
   } else {
   }
   if (i<sz) { /* Initialize info for next group */
    gp = C[i].gp;
    fprintf (out,"  Group %d: ",gp+1);
    pstr[0]=0;
   } else {
   }
  } else {
  }
 if (i==sz) break; /* Add this point to group string */
  sprintf (istr,"%d, ",C[i].id+1);
  strcat (pstr,istr);
  i++;
 }
}