Magic Sticks

Key intuition is largest area arrangement of a perimeter is when vertices lie along a circle. Cannot directly calculate, so have to binary search search it.

1. check if segments satisfy triangle inequality
2. start with circle equal in diameter to longest edge
3. place all points along perimeter in turn
   1. place the first point at 0 rad
   2. figure out angle needed to next point based on circle radius and segment length
   3. figure out if you subtended more or fewer than 2-pi rads
   • if we went around too far, it means the circle will need to grow and the shape will subtend the whole circle
   • if we didn't go around far enough, it means the circle will still need to grow (it has too because longest edge is diameter already!) but the shape will exist only in a sector subtended by the longest edge
4. for the first case, simply binary search the circle radius until you get exactly 2-pi
5. for the second case, binary search until you get the angle of the all the shorter edges to match that of the longest edge
6. remove the longest edge from the group and recurse on both sides, in case this yields a higher result (which it will if your edges are borderline on the triangle inequality)

import java.util.Scanner;
public class g {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new g().go();
	}
	private void go() {
		int cnum=0;
		while(true){
			cnum++;
			int n=in.nextInt();
			if(n==0)break;
			int[] s=new int[n];
			for(int i=0;i<n;i++)s[i]=in.nextInt();
			System.out.printf("Case %d: %.10f\n", cnum,area(s,0,s.length));
		}
	}
	private double area(int[] s, int start, int length) {//find the maximum area from s[start] to s[start+length-1]
		if(length<3)return 0;
		int max=0;
		int tot=0;
		int imax=0;
		for(int i=start;i<start+length;i++){//find longest edge
			if(s[i]>max){
				max=s[i];
				imax=i;
			}
			tot+=s[i];
		}
		if(max>=tot/2D)return area(s,start,imax-start)+area(s,imax+1,length-(imax-start)-1);//check triangle ineq
		double r=max/2D;//set radius such that longest edge is on a diameter
		double lo=r;
		double hi;
		double ans=0;
		if(degcnt(s,start,length,r,imax)>2*Math.PI){//if circle is too small, shape is whole circle
			while(degcnt(s,start,length,r,imax)>=2*Math.PI)r*=2;//make radius big enough
			hi=r;
			r/=2;
			while(true){//binary search
				double tmp=degcnt(s,start,length,r,imax);
				if(tmp<2*Math.PI){
					hi=r;
					r=(r-lo)/2+lo;
				}
				if(tmp>2*Math.PI){
					lo=r;
					r=(hi-r)/2+r;
				}
				if(Math.abs(tmp-2*Math.PI)<.000000000001)break;
			}
			for(int i=start;i<start+length;i++)ans+=s[i]/2D*Math.sqrt(r*r-Math.pow(s[i]/2D, 2));//calculate area
		}else{//else circle too big, meaning shape is only in half the circle
			while(smalldegcnt(s,start,length,r,imax)<=2*Math.PI)r*=2;//make circle big enough..should never be called
			hi=r;
			r/=2;
			while(true){//binary search
				double tmp=smalldegcnt(s,start,length,r,imax);
				if(tmp<2*Math.PI){
					lo=r;
					r=(hi-r)/2+r;
				}
				if(tmp>2*Math.PI){
					hi=r;
					r=(r-lo)/2+lo;
				}
				if(Math.abs(tmp-2*Math.PI)<.000000000001)break;
			}
			for(int i=start;i<start+length;i++)ans+=s[i]/2D*Math.sqrt(r*r-Math.pow(s[i]/2D, 2));//calculate area
			ans-=2*(s[imax]/2D*Math.sqrt(r*r-Math.pow(s[imax]/2D, 2)));
		}
		return Math.max(ans, area(s,start,imax-start)+area(s,imax+1,length-(imax-start)-1));//return max of this or removing longest edge
	}
	private double smalldegcnt(int[] s, int start, int length, double r,int imax) {//shape is on one side of circle
		double ans=0;
		for(int i=start;i<start+length;i++)ans+=2*Math.asin(s[i]/2D/r);
		return ans+2*Math.PI-4*Math.asin(s[imax]/2D/r);
	}
	private double degcnt(int[] s, int start, int length, double r,int imax) {//shape covers whole circle
		double ans=0;
		for(int i=start;i<start+length;i++)ans+=2*Math.asin(s[i]/2D/r);
		return ans;
	}
}
//Magic Sticks
//geometry
//polygon area
//binary search
//dp