题目大意：在矩形中找到一个点，使其跟最近的点距离最大
算法：模拟退火
模拟退火博大精深。。。
#include#include #include #include #include #include #include #define max( x , y ) ( ( x ) > ( y ) ? ( x ) : ( y ) )#define min( x , y ) ( ( x ) < ( y ) ? ( x ) : ( y ) )#define FOR( TMP , ST , ED ) for ( int TMP = ( ST ) ; TMP < ( ED ) ; TMP ++ )#define RORD( TMP , ST , ED ) for ( int TMP = ( ST ) ; TMP > ( ED ) ; TMP ++ )const int max_int = ( 2147483467 ) , oo = ( 1e9 ) ;using namespace std ;const int maxn = ( 1e3 + 10 ) , Num = ( 30 ) ;int N , Kuan , Chang ;double X[ Num ] , Y[ Num ] , Dis[ Num ] , data[ maxn ][ 2 ] ;#define sqr( x ) ( ( x ) * ( x ) )inline double Get( double ST_x , double ST_y ){ double ans = ( double ) oo ; FOR ( i , 0 , N ) ans = min( ans , sqrt( sqr( ST_x - data[ i ][ 0 ] ) + sqr( ST_y - data[ i ][ 1 ] ) ) ) ; return ans ;}int main(){ freopen( "poj1379.in" , "r" , stdin ) , freopen( "poj1379.out" , "w" , stdout ) ; int Test ; srand( time( 0 ) ) ; for ( scanf( "%d" , &Test ) ; Test -- ; ) { cout << "The safest point is " ; scanf( "%d%d%d" , &Kuan , &Chang , &N ) ; FOR ( i , 0 , N ) scanf( "%lf%lf" , &data[ i ][ 0 ] , &data[ i ][ 1 ] ) ; FOR ( i , 0 , Num ) { X[ i ] = rand() % Kuan + 0.01 , Y[ i ] = rand() % Chang + 0.01 ; Dis[ i ] = Get( X[ i ] , Y[ i ] ) ; } double T = ( double ) max( Kuan , Chang ) / sqrt( ( double ) Num ) , Dec = 0.80 ; double eps = ( 1e-7 ) , Pi = asin( 1.0 ) * 2.0 ; for ( ; T >= eps ; T *= Dec ) FOR ( i , 0 , Num ) FOR ( j , 0 , Num ) { double xx , yy , New , Yzx = ( ( double ) rand() / 32768.0 ) * 2.0 * Pi ; xx = X[ i ] + cos( Yzx ) * T , yy = Y[ i ] + sin( Yzx ) * T ; New = Get( xx , yy ) ; if ( New > Dis[ i ] && xx >= 0 && xx <= Kuan && yy >= 0 && yy <= Chang ) Dis[ i ] = New , X[ i ] = xx , Y[ i ] = yy ; } double Ans = ( double ) - oo , xx , yy ; FOR ( i , 0 , Num ) if ( Ans < Dis[ i ] ) Ans = Dis[ i ] , xx = X[ i ] , yy = Y[ i ] ; printf( "(%.1lf, %.1lf).\n" , xx , yy ) ; } return 0 ;}