LOJ 1240

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

///constant
#define eps 1e-6
#define max 1e9

struct point{
    double x,y,z;

}A,B,P,temp;

struct point Scan(){scanf("%lf %lf %lf",&temp.x,&temp.y,&temp.z);return temp;}

double SQR(double p){return p*p;}

double differ(struct point P,struct point Q){return SQR(P.x-Q.x)+SQR(P.y-Q.y)+SQR(P.z-Q.z);}

struct point DIV(struct point P,struct point Q,double m,double n)
{
    temp.x=(m*Q.x+n*P.x)/(m+n);
    temp.y=(m*Q.y+n*P.y)/(m+n);
    temp.z=(m*Q.z+n*P.z)/(m+n);
    return temp;
}

double min(double x,double y){return (x<y)?x:y;}

double Ternarysearch(struct point loAB,struct point hiAB,struct point P,int depth)
{
    if(depth>50){
        return max;
    }
    struct point midAB1,midAB2;
    double diff1,diff2,diff;
    midAB1=DIV(loAB,hiAB,1,2);
    midAB2 = DIV(midAB1,hiAB,1,1);
    diff1 = differ(midAB1,P);
    diff2 = differ(midAB2,P);
    if(diff1<diff2){
        diff = Ternarysearch(loAB,midAB2,P,depth+1);
    }
    else{
        diff = Ternarysearch(midAB1,hiAB,P,depth+1);
    }
    return min(min(diff,diff1),min(diff,diff2));
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
	    A=Scan();B=Scan();P=Scan();;
	    printf("Case %d: %lf\n",i,sqrt(Ternarysearch(A,B,P,0)));
	}
	return 0;
}