hdu 3263 Ancient vending machine(二)
}
//两直线交点
point crosspoint( line l, line m )
{
point a = point( m.x, m.y );
point b = point( m.x+m.dx, m.y+m.dy );
if ( m.dx*l.dy == m.dy*l.dx ) {
if ( dist( point( l.x, l.y ), a ) < dist( point( l.x, l.y ), b ) )
return a;
else return b;
}else {
double a1 = -l.dy,b1 = l.dx,c1 = l.dx*l.y-l.dy*l.x;
double a2 = -m.dy,b2 = m.dx,c2 = m.dx*m.y-m.dy*m.x;
double x = (c1*b2-c2*b1)/(a1*b2-a2*b1);
double y = (c1*a2-c2*a1)/(b1*a2-b2*a1);
return point( x, y );
}
}
//计算空的最大长度
double Calcul( int N )
{
H[N] = H[0];
point X[ 21 ];
double D = 0.0;
for ( int i = 0 ; i < N ; ++ i )
for ( int j = i+1 ; j < N ; ++ j ) {
line l = line( H[i], H[j] );
int S = 0;
for ( int k = 0 ; k < N ; ++ k ) {
line m = line( H[k], H[k+1] );
if ( l_cross_s( l, m ) )
X[S ++] = crosspoint( l, m );
}
X[S ++] = H[i];
X[S ++] = H[j];
P0 = point( -101, -103 );
for ( int k = 0 ; k < S ; ++ k )
X[k].d = dist( P0, X[k] );
sort( X, X+S, cmp2 );
double sum = 0.0;
int fla = 0;
for ( int i = 1 ; i < S ; ++ i ) {
if ( in( point( (X[i-1].x+X[i].x)/2, (X[i-1].y+X[i].y)/2 ), H, N ) ) {
if ( fla ) sum += dist( X[i-1], X[i] );
else sum = dist( X[i-1], X[i] );
D = max( D, sum );
fla = 1;
}
}
}
return D;
}
int main()
{
int T,N,M;
while ( scanf("%d",&T) != EOF )
while ( T -- ) {
scanf("%d",&N);
for ( int i = 0 ; i < N ; ++ i )
scanf("%lf%lf",&H[i].x,&H[i].y);
scanf("%d",&M);
for ( int i = 0 ; i < M ; ++ i )
scanf("%lf%lf",&C[i].x,&C[i].y);
//计算硬币最小宽度
double d = Graham( M );
//计算空的最大长度
double D = Calcul( N );
if ( d <= D ) printf("legal\n");
else printf("illegal\n");
}
return 0;
}