http://acm.fzu.edu.cn/problem.php?pid=1918

2010福州邀请赛 J 题

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<complex>
using namespace std;

typedef complex<double> point;
const int maxn = 80010;
const double pi = acos( -1.0 );
const double eps = 1e-8;

//struct poly
//{
//    point p[maxn];
//    int n;
//};
//poly P[11];
struct node
{
    double x1, x2;
    bool operator<( const node & b )
    {
        return x1 < b.x1;
    }
};
node a[maxn*10];
point dir[4];

double operator^( point p1, point p2 ){ return imag( conj( p1 ) * p2 ); }
double operator&( point p1, point p2 ){ return real( conj( p1 ) * p2 ); }
int dblcmp( double x ){ return ( x < -eps ? - 1 : x > eps ); }

int main( )
{
    int t, n, i, j, polynum, len, d, k = 1;
    point Q, S, s, e;
    char c[3];
    double x, y, sita1, sita2, total;
    dir[0] = point( 0.0, 1.0 );  dir[1] = point( -1.0, 0.0 );
    dir[2] = point( 0.0, -1.0 );  dir[3] = point( 1.0, 0.0 );
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%d%lf%lf",&polynum,&x,&y);
        Q = point( x, y );
        len = 0;
        for( i = 0; i < polynum; i++ )
        {
            scanf("%d%lf%lf",&n,&x,&y);
            s = point( x, y );
            d = 0;
            for( j = 0; j < n; j++ )
            {
                scanf("%s",c);
                switch( c[0] )
                {
                case 'F':
                    scanf("%lf",&x);
                    e = s + x * dir[d];
                    if( dblcmp( s - Q ^ e - Q ) != 0 )
                    {
                        sita1 = arg( e - Q );
                        sita2 = arg( s - Q );
                        if( sita1 < sita2 )
                        {
                            if( !( sita1 < -pi / 2.0 && sita2 > pi / 2.0 ) )
                            {
                                a[len].x1 = sita1;
                                a[len++].x2 = sita2;
                            }
                            else 
                            {
                                a[len].x1 = -pi;
                                a[len++].x2 = sita1;
                                a[len].x1 = sita2;
                                a[len++].x2 = pi;
                            }
                        }
                        else if( sita2 < sita1 )
                        {
                            if( !( sita2 < -pi / 2.0 && sita1 > pi / 2.0 ) )
                            {
                                a[len].x1 = sita2;
                                a[len++].x2 = sita1;
                            }
                            else 
                            {
                                a[len].x1 = -pi;
                                a[len++].x2 = sita2;
                                a[len].x1 = sita1;
                                a[len++].x2 = pi;
                            }
                        }
                    }
                    s = e;
                    break;
                case 'L':
                    d = ( d + 1 ) % 4;
                    break;
                case 'R':
                    d = ( d + 3 ) % 4;
                    break;
                }
            }
        }
        sort( a, a + len );
        total = 2 * pi;
        x = a[0].x1; y = a[0].x2;
        for( i = 1; i < len; i++ )
        {
            if( y >= a[i].x1 && y < a[i].x2 )
                y = a[i].x2;
            else if( a[i].x1 > y )
            {
                total -= ( y - x );
                x = a[i].x1;
                y = a[i].x2;
            }
        }
        total = total - ( y - x );
        total = total * 180 / pi;
        printf("Case %d: %.2lf\n", k++, total);
    }
    return 0;
}