Smile

#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);
            }
        }

}