Poj Solution 2500

http://poj.org/problem?id=2500

#include <iostream>
#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%.6lfnn", h, s/10000 );
    }

    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *