#include "stdio.h"
#include "math.h"
#define max_isl 15
#define and &&
#define or ||

int ant_poly;
int size[max_isl];
int poly[max_isl][26][3];
int farge[max_isl];
int kant[15*15*26*26][7];

main()
{
 int korteste;
 int ant_funnet;
 FILE *fp1,*fp2;
 int l,k,i,j;
 int x_c,y_c;
 int ant_inst;
 int ant_hjorner;
 int ant_kant;
 int ok_kant();
 int jj,kk,g_f;
 float tot_lengde;

 fp1 = fopen("islands.in","r");
 fp2 = fopen("islands.out","w");

 fscanf(fp1,"%d",&ant_inst);

 for(i=1;i<=ant_inst;i++)
 {
  fscanf(fp1,"%d \n",&ant_poly);

  for(j=1;j<=ant_poly;j++)
  {
   fscanf(fp1,"%d ",&ant_hjorner);
   size[j] = ant_hjorner;

   for(k=1;k<=ant_hjorner;k++)
   {
    fscanf(fp1,"%d %d",&x_c,&y_c);
    poly[j][k][1] = x_c;
    poly[j][k][2] = y_c;
   }
  }

/* Ferdig å lese inn, finner alle mulige kanter */
/*
  printf("Ferdig å lese inn \n");
*/

  ant_kant = 0;
  for(j=1;j<ant_poly;j++)
    for(jj=1;jj<=size[j];jj++)
      for(k=j+1;k<=ant_poly;k++)
        for(kk=1;kk<=size[k];kk++)
        {
         if (ok_kant(poly[j][jj][1],poly[j][jj][2],poly[k][kk][1],poly[k][kk][2]) )
         {
          ant_kant++;
          kant[ant_kant][1] = poly[j][jj][1];
          kant[ant_kant][2] = poly[j][jj][2];
          kant[ant_kant][3] = poly[k][kk][1];
          kant[ant_kant][4] = poly[k][kk][2];
          kant[ant_kant][5] = j;
          kant[ant_kant][6] = k;
/*
          printf("Har funnet kant nr %d \n",ant_kant);
          printf("Fra %d,%d til %d,%d \n",kant[ant_kant][1],kant[ant_kant][2],kant[ant_kant][3],kant[ant_kant][4]);
*/
         }
        }
 
/* Finn korteste kant ant_poly-1 ganger*/


   ant_funnet = 0;
   tot_lengde = 0.0;
   for(k=1;k<=ant_poly;k++)
     farge[k] = k;

   while (ant_funnet < ant_poly-1)
   {
    korteste = 0;
    for(k=1;k<=ant_kant;k++)
      if (kant[k][5] != 0 and lengde(k) < lengde(korteste))
        korteste = k;
    
    if (farge[kant[korteste][5]] != farge[kant[korteste][6]])
    {
/*
     printf("Velger kant fra %d,%d til %d,%d \n",kant[korteste][1],kant[korteste][2],kant[korteste][3],kant[korteste][4]);
*/
     g_f = farge[kant[korteste][5]];
     for(k=1;k<=ant_poly;k++)
       if (farge[k] == g_f)
         farge[k] = farge[kant[korteste][6]];
     ant_funnet++;
     tot_lengde += sqrt((float)lengde(korteste));
    }
    else
/*
     printf("Velger ikke kant fra %d,%d til %d,%d \n",kant[ant_kant][1],kant[ant_kant][2],kant[ant_kant][3],kant[ant_kant][4]);
*/
    kant[korteste][5] = 0;
   }
 
  fprintf(fp2,"The minimal interconnect consists of %d bridges\n",ant_poly-1);
  fprintf(fp2,"with a total length of %4.3f.\n",tot_lengde);
 }
 
 fclose(fp2);

}

int lengde(k)
int k;
{
 int l1,l2;

 if (k == 0)
   return(999999);

 l1 = kant[k][1] - kant[k][3];
 l1 = l1*l1;
 l2 = kant[k][2] - kant[k][4];
 l2 = l2*l2;
 return(l1+l2);
}


int retning(x1,y1,x2,y2,x3,y3)
int x1,y1,x2,y2,x3,y3;
{
 int v1,w1,v2,w2;

 v1 = x3 - x1;
 w1 = y3 - y1;
 v2 = x2 - x1;
 w2 = y2 - y1;

 return(v1*w2 - v2*w1);

}

int on_segment(x1,y1,x2,y2,x3,y3)
int x1,y1,x2,y2,x3,y3;
{
 int minx,maxx,miny,maxy;
 minx = x1;
 if (minx > x2)
   minx= x2;
 maxx = x1;
 if (maxx < x2)
   maxx = x2;

 miny = y1;
 if (miny > y2)
   miny= y2;
 maxy = y1;
 if (maxy < y2)
   maxy = y2;

 if ((minx <= x3) and (x3 <= maxx) and
     (miny <= y3) and (y3 <= maxy))
   return(1);
 else
   return(0);
}


int krysser(x1,y1,x2,y2,x3,y3,x4,y4)
int x1,y1,x2,y2,x3,y3,x4,y4;
{
 int retning();
 int on_segment();
 int d1,d2,d3,d4;

 d1 = retning(x3,y3,x4,y4,x1,y1);
 d2 = retning(x3,y3,x4,y4,x2,y2);
 d3 = retning(x1,y1,x2,y2,x3,y3);
 d4 = retning(x1,y1,x2,y2,x4,y4);

 if (((d1>0 and d2<0) or (d1<0 and d2>0)) and
     ((d3>0 and d4<0) or (d3<0 and d4>0)))
   return(1);

 if (d1 == 0 and on_segment(x3,y3,x4,y4,x1,y1))
   return(1);

 if (d2 == 0 and on_segment(x3,y3,x4,y4,x2,y2))
   return(1);

 if (d3 == 0 and on_segment(x1,y1,x2,y2,x3,y3))
   return(1);

 if (d4 == 0 and on_segment(x1,y1,x2,y2,x4,y4))
   return(1);

 return(0);
}

int ok_kant(x1,y1,x2,y2)
int x1,y1,x2,y2;
{
 int i,j,k;
 int ekte_kant;
 int krysser();
 int n,test;

 ekte_kant = 1;
 for(i=1;i<=ant_poly;i++) 
 {
   n = size[i];
   for(j=1;j<size[i];j++)
   {
     test = 1;
     if (x1==poly[i][j][1] and y1==poly[i][j][2])
       test = 0;
     if (x1==poly[i][j+1][1] and y1==poly[i][j+1][2])
       test = 0;
     if (x2==poly[i][j][1] and y2==poly[i][j][2])
       test = 0;
     if (x2==poly[i][j+1][1] and y2==poly[i][j+1][2])
       test = 0;

     if (test)
       if (krysser(x1,y1,x2,y2,poly[i][j][1],poly[i][j][2],poly[i][j+1][1],poly[i][j+1][2]))
         ekte_kant = 0;
   }
   test = 1;
   if (x1==poly[i][n][1] and y1==poly[i][n][2])
     test = 0;
   if (x1==poly[i][1][1] and y1==poly[i][1][2])
     test = 0;
   if (x2==poly[i][n][1] and y2==poly[i][n][2])
     test = 0;
   if (x2==poly[i][1][1] and y2==poly[i][1][2])
     test = 0;
   if (test)
     if (krysser(x1,y1,x2,y2,poly[i][n][1],poly[i][n][2],poly[i][1][1],poly[i][1][2]))
       ekte_kant = 0;
 }

 return(ekte_kant);
}