#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
int const max_n = 25;
double const INF = 1.7976931348623158e+308;
int x,y,n;
double a[max_n/2][2];
double ans;
int cap[2*max_n][2*max_n];
double cost[2*max_n][2*max_n];
int flow[2*max_n][2*max_n];
double dis( double x1,double y1,double x2,double y2 ){
double temp = ( sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) + sqrt( (x1-x)*(x1-x) + (y1-y)*(y1-y) ));
//printf("%.2lf %.2lf %.2lf %.2lf %.2lf\n",x1,y1,x2,y2,temp);
return temp;
}
void init(){
scanf("%d%d",&x,&y);
scanf("%d",&n);
for( int i=0; i<2*n; i++ )
scanf("%lf%lf",&a[i][0],&a[i][1]);
memset(cap,0,sizeof(cap));
for( int i=0; i<2*max_n; i++ )
for( int j=0; j<2*max_n; j++ )
cost[i][j] = 0.0;
for( int i=1; i<= 4*n; i++ ){
cap[0][i] = 1;
cap[i][4*n+1] = 1;
}
for( int i=1; i<=4*n ; i++ )
for( int j=i+1; j<=4*n; j++ )
if( i != j )
cap[i][j] = 1;
for( int i=0; i<2*n; i++)
for( int j=i+1; j<2*n; j++)
if( i != j ){
cost[i+1][j+1] = min ( dis(a[i][0],a[i][1],a[j][0],a[j][1]),dis( a[j][0],a[j][1],a[i][0],a[i][1]) );
cost[j+1][i+1] = - cost[i+1][j+1];
cap[0][i+1] = 1;
cap[i+1][j+1] = 1;
cap[j+1][2*n+1] = 1;
cost[2*n+i+1][2*n+j+1] = cost[i+1][j+1];
cost[2*n+j+1][2*n+i+1] = - cost[2*n+i+1][2*n+j+1];
}
for( int i=0; i<=2*n+1; i++ ){
for( int j=0; j<=2*n+1; j++)
printf("%.2lf ",cost[i][j]);
printf("\n");
}
for( int i=0; i<=2*n+1; i++ ){
for( int j=0; j<=2*n+1; j++)
printf("%d ",cap[i][j]);
printf("\n");
}
}
void minflow(){
queue<int> q;
double d[2*max_n];
memset(flow,0,sizeof(flow));
ans = 0.0;
int max_f = 0;
int s = 0;
int t = 4*n + 1;
int id = 0;
for( ; ; ){
//bellman_ford_begin
bool inq[2*max_n];
int pa[2*max_n];
for( int i=0; i<=t; i++ )
pa[i] = i;
for( int i=0; i<=t; i++ )
d[i] = (i==s?0:INF);
memset(inq,0,sizeof(inq));
q.push(s);
while( !q.empty() ){
int u = q.front();
q.pop();
inq[u] = false;
for( int v=0; v<=t; v++ )
if( cap[u][v] > flow[u][v] && d[v]>d[u]+cost[u][v] ){
d[v] = d[u] + cost[u][v];
pa[v] = u;
if( !inq[v] ){
inq[v] = true;
q.push(v);
}
}
}
// bellman_ford_end
if( d[t] == INF )
break;
printf("d[t] = %.2lf\n",d[t]);
//t不可达，表示当前流为所求
int a = 1;
/*for( int u=t; u!=s; u = pa[u] )
if( a< cap[pa[u]][v] = -flow[pa[u]][v] )
a = cap[pa[u]][v] = -flow[pa[u]][v];*/
//计算可改进量
for( int u=t; u!=s; u=pa[u] ){//增广
printf("u = %d\n",u);
flow[pa[u]][u] = +a;
flow[u][pa[u]] -= a;//flow = -flow
}
ans += d[t];
printf("ans = %.2lf\n",ans);
max_f++;
}
printf("max_f = %d\n",max_f);
}
int main(){
int t;
while( ~scanf("%d",&t) ){
int id = 0;
while( t-- ){
init();
minflow();
printf("Case #%d: %.2lf\n",++id,ans/2);
}
}
}