gistfile1.cpp

#include<iostream>
#include<cmath>
#include<stdio.h>
#define fr(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=1002;
const double pi=acos(-1.0);
const double limit=1e8;
const double zero=1e-10;
double s[maxn];
int i,n,ca=0;
double angle(double s,double r){
	return 2*asin(s/2/r);
}
double area(double s,double r){
	double h=sqrt(r*r-(s/2)*(s/2));
	return h*s/2;
}
double search1(int a,int b,int large,double le,double ri){
	double mid=(le+ri)/2;
	if(ri-le<zero){
		double sum=0;
		fr(i,a,b)
			if(i==large)
				sum-=area(s[i],mid);
			else
				sum+=area(s[i],mid);				
		return sum;
	}
	double other=0;
	fr(i,a,b)
		if(i!=large)
			other+=angle(s[i],mid);
	if(angle(s[large],mid)<other)
		return search1(a,b,large,le,mid);
	else
		return search1(a,b,large,mid,ri);
}
double search2(int a,int b,int large,double le,double ri){
	double mid=(le+ri)/2;
	if(ri-le<zero){
		double sum=0;
		fr(i,a,b)
			sum+=area(s[i],mid);
		return sum;		
	}
	double tot=0;
	fr(i,a,b)
		tot+=angle(s[i],mid);
	if(tot<2*pi)
		return search2(a,b,large,le,mid);
	else
		return search2(a,b,large,mid,ri);
}
double get(int a,int b){
	int large=a;
	fr(i,a,b)
		if(s[i]>s[large])
			large=i;
	double other=0,tot=0;
	fr(i,a,b)
		if(i!=large)
			other+=s[i];
	if(other<=s[large]+zero)
		return 0;
	fr(i,a,b)
		if(i!=large)
			tot+=angle(s[i],s[large]/2);
	if(tot<pi)
		return search1(a,b,large,s[large]/2,limit);
	else
		return search2(a,b,large,s[large]/2,limit);
}
double dfs(int a,int b){
	if(b-a+1<3)
		return 0;
	int large=a;
	fr(i,a,b)
		if(s[i]>s[large])
			large=i;
	return max(get(a,b),dfs(a,large-1)+dfs(large+1,b));	
}
int main(){
	cin>>n;
	while(n>0){
		fr(i,1,n)
			cin>>s[i];
		printf("Case %d: %.6lf\n",++ca,dfs(1,n));
		cin>>n;
	}
}