http://acm.fzu.edu.cn/problem.php?pid=19182010福州邀请赛 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;
}
|