/*
 * @(#) msu98_a.c - Problem 'A' ("Cockroach") solution
 * of the ACM Programming Contest at the MSU in 1998.
 * (c) 1998 Ivan Maidanski <ivmai@chat.ru> http://ivmai.chat.ru
 * Freeware program source. All rights reserved.
 **
 * Language: ANSI C
 * Tested with: Borland C++ v3.1
 * Last modified: 1998-10-07 22:10:00 GMT+04:00
 */

/* Input data file: a.dat */

#include <stdlib.h> /* malloc(), free() */
#include <stdio.h> /* FILE, fopen(), fscanf(), printf() */
#include <math.h> /* sqrt() */

#define N 50

#define INFINITY (1.0/0)

int n,m;
int x1[N],y1[N],x2[N],y2[N];
int xp[2+4*N],yp[2+4*N];
float *pd[2+4*N];

void adjcoord(int *a, int *b)
{
 int t;
 if (*a>*b)
 {
  t=*a;
  *a=*b;
  *b=t;
 }
}

int isinner(int x, int y)
{
 int i;
 for (i=0;i<n;i++)
  if (x1[i]<x && x<x2[i] && y1[i]<y && y<y2[i])
   return 1;
 return 0;
}

int isadded(int x, int y)
{
 int p;
 for (p=0;p<m;p++)
  if (x==xp[p] && y==yp[p])
   return 1;
 return 0;
}

int across(int xa, int ya, int xb, int yb)
{
 int i;
 adjcoord(&xa,&xb);
 adjcoord(&ya,&yb);
 for (i=0;i<n;i++)
  if (xa<x2[i] && x1[i]<xb && ya<y2[i] && y1[i]<yb)
   return 1;
 return 0;
}

int main()
{
 FILE *f=fopen("a.dat","rt");
 int k,curk;
 int i,j,p,t;
 float dcur;
 fscanf(f,"%*[^-0-9]%d",&k);
 for (curk=1;curk<=k;curk++)
 {
  fscanf(f,"%*[^-0-9]%d%*[^-0-9]%d%*[^-0-9]%d%*[^-0-9]%d%*[^-0-9]%d",
         xp,yp,xp+1,yp+1,&n);
  for (i=0;i<n;i++)
  {
   fscanf(f,"%*[^-0-9]%d%*[^-0-9]%d%*[^-0-9]%d%*[^-0-9]%d",
          x1+i,y1+i,x2+i,y2+i);
   adjcoord(x1+i,x2+i);
   adjcoord(y1+i,y2+i);
  }
  printf("##### %d\n",curk);
  if (isinner(xp[0],yp[0]))
    printf("Cockroach's position is invalid.\n");
  if (isinner(xp[1],yp[1]))
   printf("Target position is invalid.\n");
  m=1;
  if (isadded(xp[1],yp[1]))
   printf("Cockroach is at the target.\n");
  if (!isinner(xp[0],yp[0]) && !isinner(xp[1],yp[1]))
  {
   m++;
   for (i=0;i<n;i++)
   {
    if (!isinner(x1[i],y1[i]) && !isadded(xp[m]=x1[i],yp[m]=y1[i]))
     m++;
    if (!isinner(x2[i],y1[i]) && !isadded(xp[m]=x2[i],yp[m]=y1[i]))
     m++;
    if (!isinner(x1[i],y2[i]) && !isadded(xp[m]=x1[i],yp[m]=y2[i]))
     m++;
    if (!isinner(x2[i],y2[i]) && !isadded(xp[m]=x2[i],yp[m]=y2[i]))
     m++;
   }
   for (i=0;i<m;i++)
    for (pd[i]=(float *)malloc(m*sizeof(float)),j=0;j<m;j++)
     pd[i][j]=+INFINITY;
   for (i=0;i<m-1;i++)
    for (j=i+1;j<m;j++)
     if (!across(xp[i],yp[i],xp[j],yp[j]))
      pd[i][j]=pd[j][i]=sqrt((float)(xp[i]-xp[j])*(xp[i]-xp[j])+
                             (float)(yp[i]-yp[j])*(yp[i]-yp[j]));
   do for (t=i=0;i<m-1;i++)
    for (j=i+1;j<m;j++)
     for (p=0;p<m;p++)
      if (dcur=pd[i][p]+pd[p][j],pd[i][j]>dcur)
       pd[i][j]=pd[j][i]=dcur,t++;
    while (t);
   if (pd[0][1]<+INFINITY)
    printf("Minimal distance is %1.2f.\n",pd[0][1]);
    else printf("Target is unreachable.\n");
   for (i=0;i<m;i++)
    free((void *)pd[i]);
  }
 }
 return 0;
}