1267.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include < stdio.h>
#include <math.h>
#include <algorithm>
#include <functional>
using namespace std;

const double eps = 1e-9;
const double pi = acos(-1);

double l[100];
int n;

int doit()
{
	int i;
	double total, a, b, c, s, temp, area, p;

	total = 0;

	if( scanf( "%d", &n ) != 1 ) return 0;
	for( i=0; i<n; i++ )
	{
		scanf( "%lf", &l[i] );
		total += l[i];
	}

	sort( l, l+n, greater<double>() );

	if( l[0] * 2 - total > -eps )
	{
		printf( "0.00\n" );
		return 0;
	}


	c = l[0] / 2;

	for( s=0,i=1; i<n; i++ )
		s += asin( l[i]/2/c );
	

	if( fabs( s - pi/2 ) < eps )
	{
		for( area=0,i=1; i<n; i++ )
		{
			p = ( 2*c + l[i] ) / 2;
			area += sqrt( p * (p-l[i]) * (p-c) * (p-c) );
		}
	}
	else if( s < pi/2 )
	{
		a = l[0]/2, b = total*10000;

		while( b - a > eps )
		{
			c = ( b + a ) / 2;

			for( s=0,i=1; i<n; i++ )
			s += asin( l[i]/2/c );

			temp = asin( l[0]/2/c );
			
		//	if( fabs( s - temp ) < eps ) break;
			if( s > temp ) b = c - eps;
			else a = c + eps;
		}
		
		while( fabs( s - temp ) > 1e-5 ) printf( "o");

		for( area=0,i=1; i<n; i++ )
		{
			p = ( 2 * c + l[i] ) / 2;
			area += sqrt( p * (p-l[i]) * (p-c) * (p-c) );
		}
		
		p = ( 2*c + l[0] ) / 2;
		area -= sqrt( p * (p-l[0]) * (p-c) * (p-c) );
	}
	else
	{
		a = l[0]/2, b = total/2;
	
		while( b - a > eps )
		{
			c = ( b + a ) / 2;
		
			for( s=0,i=0; i<n; i++ )
			{
				temp = asin( l[i]/2/c );
				s += temp;
			}

	//		if( fabs( s - pi ) < eps ) break;
			
			if( s > pi ) a = c + eps;
			else b = c - eps;
		}
		
		while( fabs( s - pi ) > 1e-5 )
			int *kl = new int[10000000];

		for( area=0,i=0; i<n; i++ )
		{
			p = ( 2*c + l[i] ) / 2;
			area += sqrt( p * (p-l[i]) * (p-c) * (p-c) );
		}
	}


	printf( "%.2lf\n", area );

	return 1;
}

int main()
{
	while( doit() )
		;
	return 0;
}