2500.txt

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

Memory:48K  Time:46MS
Language:C++  Result:Accepted

Source 

#include <iostream.h>
#include <math.h>
#include <algorithm>

using namespace std;


int n,c,g;
double d,r;
const double pi = 3.1415926535898;
const double eps = 1e-8;

double area(int a, int b, int c )
{
	double l1, l2;
	l1 = sin( pi*abs(a-b)/n ) * r;
	l2 = sin( pi*abs(b-c)/n ) * r;
	return l1 * l2 * sin( pi*abs(a-c)/n ) * 2;
}

int id[1000];

void init()
{
	int k;

	cin>>d>>n>>c>>g;
	r = d *100 / 2;

	id[0] = 0;
	for( k=1; k<c; k++ )
		id[k] = ( id[k-1] + g ) % n;
	
	sort( id, id+c );
	c = unique_copy( id, id+c, id ) - id;
}

int main()
{
	int i, j, k, cas, h;
	double s, s1, s2, t1, t2;
	
	cin>>cas;
	for( h=1; h<=cas; h++ )
	{
		init();

		s = 0;
		for( i=2, j=1, k=3; i < c-1; i++ )
		{
			if( k < i+1 ) k = i+1;

			s1 = area( 0, id[j], id[i] );
			s2 = area( id[i], id[k], 0 );

			while( j+1 < i && ( t1 = area( 0, id[j+1], id[i] ) ) - s1 > -eps )
			{
				s1 = t1;
				j++;
			}

			while( k+1 < c && ( t2 = area( 0 , id[i], id[k+1] ) ) - s2 > -eps )
			{
				s2 = t2;
				k++;
			}
			if( s1 + s2 - s > -eps ) s = s1 + s2;
		}
		printf( "Scenario #%d:\n%.6lf\n\n", h, s/10000 );
	}

	return 0;
}