toj_2942_1.cpp

Tianjin University Online Judge 的80多道题目 .

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;

#define MINNUM 1e-10
#define MAXNUM 10010
struct Point 
{
    double x;
    double y;
};

Point p[ 2 ][ MAXNUM ];
int n , m;
double minDis;
inline int sigDbl( double x )
{
    if( fabs( x ) < MINNUM )
        return 0;
    else if(  x  > 0 )
        return 1;
    else
        return -1;
}

void readP( int aP , int num )
{
    int i , j;
    for( i = 0; i < num; i++ )
        scanf( "%lf%lf" , &p[ aP ][ i ].x , &p[ aP ][ i ].y );
    p[ aP ][ num ] = p[ aP ][ 0 ];
    
}

inline double dotMul( Point a, Point b )
{
    return ( a.x * b.x  + a.y * b.y );
}

inline Point vec( Point a , Point b )
{
    Point ab;
    ab.x = b.x - a.x;
    ab.y = b.y - a.y;
    return ab;
}

inline double vecLen( Point a )
{
    return sqrt(  a.x * a.x + a.y * a.y );
}

inline double area( Point a , Point b )
{
    return fabs( a.x * b.y - b.x * a.y );
}

inline double findDis( Point a , Point b , Point c )
{
    double s1 , s2;
    Point ba , bc , ca;
    ba = vec( b , a );
    bc = vec( b , c );
    ca = vec( c , a );
    s1 = dotMul( ba , bc  );
    s2 = - dotMul( ca , bc );
    if( sigDbl( s1 ) >= 0 && sigDbl( s2 ) >= 0  ){
        return  area( ba, ca ) / vecLen( bc );
    }
    else
    	return min( vecLen( ba ) , vecLen( ca ) );
/*    else if ( sigDbl( s1 ) < 0 && sigDbl( s2 ) > 0 )
        return vecLen( ba );
    else
        return vecLen( ca );*/
}


void findMin( int p1 , int num1 , int p2 , int num2 )
{
    int i , j , k;
    double aDis;
    
    for( i = 0; i < num1; i++ ){
        for( j = 0; j < num2; j++ ){
            aDis = findDis( p[ p1 ][ i ] , p[ p2 ][ j ] , p[ p2 ][ j + 1 ] );
//            printf( "%.2lf %.2lf %.2lf %.2lf %.2lf %.2lf %.2lf\n" , p[ p1 ][ i ].x , p[ p1 ][ i ].y , p[ p2 ][ j ].x , p[ p2 ][ j ].y  , p[ p2 ][ j + 1 ].x , p[ p2 ][ j + 1 ].y , aDis );
            if( aDis < minDis )
                minDis = aDis;
        }
    }
}

int main()
{
    int i ,j;
//   freopen( "toj_2942_in_1.txt" , "r" , stdin );
//  freopen( "toj_2942_1_out_1.txt" , "w" , stdout );
    
    while ( scanf( "%d%d" , &n ,&m )  != EOF &&  n  &&  m  ){
        readP( 0 , n );
        readP( 1 , m );
        minDis = 1e30;
//   
        findMin( 1 , m , 0 , n );
             findMin( 0 , n , 1 , m );
        printf( "%.2lf\n" , minDis );
    }
    return 0;
}