toj_2942.cpp

Tianjin University Online Judge 的80多道题目 .

#include<cstdio>
#include<cstdlib>
#include<cmath>
#define MAXLEN 1010
#define MAXDISTANCE 1e20

struct Point
{
    int x;
    int y;
};

    
struct Polygon
{
    Point point[ MAXLEN ];
    int num;
};

double minDistance;
double distance[ MXLEN ];

struct Distance 
{
    double d[ MAXLEN ];
    int num;
};
Distance distance;

int compare( double const *a , double const * b )
{
    return *a - *b;
}




void findMin( const double&  d )
{
    if( d < minDistance )
        minDistance = d;
}

double findDistance( Point * p1 , Point* p2 )
{
    return sqrt( ( p1-> x - p2->x ) * ( p1-> x  - p2-> x ) + ( p1->y - p2-> y ) * ( p1-> y - p2 -> y ) );
}

void findPoint2Edge( Polygon ap , Polygon bp )
{
    int i , j;
    double aDistance , p0_p1 , p0_p2;
    Point *p2 , *p1 , *p0 , *p3;
    
    for( i = 0; i < ap.num; i++ )
        for( j = 0; j < bp.num ; j++ ){
            p0 = &ap.point[ i ];
            p1 = &bp.point[ j ];
            p2 = &bp.point[ ( j + 1 ) % bp.num ];
            aDistance = static_cast < double >( abs( ( p2->y - p1-> y ) * ( p0->x - p1->x ) - ( p2->x - p1->x ) * ( p0->y - p1->y ) ) ) / sqrt( ( p2->y - p1->y ) * ( p2->y - p1->y ) + ( p2->x - p1->x ) * ( p2->x - p1->x ) );
            p0_p1= findDistance( p0 , p1 );
            p0_p2 = findDistance( p0 , p2 );
            if( p0_p1 > p0_p2 ){
                p3 = p1;
                p1 = p2;
                p2 = p3;
            }
            if(   ( ( p0->x - p1->x ) * ( p2->x - p1-> x ) + ( p0->y - p1->y ) * ( p2->y - p1->y ) ) < 0 )
                aDistance = p0_p1;
            findMin( aDistance );
            distance.d[ distance.num++ ] = aDistance;
            
        }
}

int main()
{
    int i , j , k;
    Polygon np , mp;
    double aDistance;
    freopen( "e:\\cpp\\toj_contest\\contest_08_3_31\\2942_in.txt" , "r" , stdin );
    freopen( "e:\\cpp\\toj_contest\\contest_08_3_31\\2942_out_my.txt" , "w"  , stdout) ;
    

    while ( scanf( "%d%d" , &np.num , &mp.num ) != EOF && np.num && mp.num ){
        for( i = 0; i < np.num; i++ )
            scanf( "%d%d" , &np.point[ i ].x  , &np.point[ i ].y );
        for( i = 0; i < mp.num; i++ )
             scanf( "%d%d" , &mp.point[ i ].x , &mp.point[ i ].y );
        minDistance = MAXDISTANCE;
        
        findPoint2Edge( np , mp );
        findPoint2Edge( mp , np );
        
        printf( "%0.2lf\n" , minDistance );
    }
    return 0;
}