题目分析:二分+并查集判断正方形的下边界是否和上边界相连,不相连则这次得到的是一个可行解,继续调整下界,否则调整上界。
代码如下:
#include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REV( i , a , b ) for ( int i = a ; i >= b ; -- i ) #define CLR( a , x ) memset ( a , x , sizeof a ) const int MAXN = 5005 ; double eps = 1e-5 ; double d[MAXN][MAXN] ; int p[MAXN] ; int rank[MAXN] ; int X[MAXN] , Y[MAXN] ; int n , L ; int find ( int x ) { return p[x] == -1 ? x : ( p[x] = find ( p[x] ) ) ; } void Union ( int x , int y ) { x = find ( x ) ; y = find ( y ) ; if ( x != y ) { if ( rank[x] <= rank[y] ) { p[x] = y ; if ( rank[x] == rank[y] ) ++ rank[y] ; } else p[y] = x ; } } double dist ( int i , int j ) { double x = X[i] - X[j] ; double y = Y[i] - Y[j] ; return sqrt ( x * x + y * y ) ; } int check ( double D ) { CLR ( rank , 0 ) ; CLR ( p , -1 ) ; REP ( i , 0 , L ) { if ( Y[i] + D >= n ) Union ( i , L ) ; if ( Y[i] - D <= 0 ) Union ( i , L + 1 ) ; REP ( j , i + 1 , L ) if ( d[i][j] <= D ) Union ( i , j ) ; } if ( find ( L ) == find ( L + 1 ) ) return 0 ; return 1 ; } void solve () { REP ( i , 0 , L ) scanf ( "%d%d" , &X[i] , &Y[i] ) ; REP ( i , 0 , L ) REP ( j , i + 1 , L ) d[i][j] = d[j][i] = dist ( i , j ) ; double l = 0 , r = MAXN ; while ( r - l > eps ) { double mid = ( l + r ) / 2 ; if ( check ( mid ) ) l = mid ; else r = mid ; } printf ( "%.3f\n" , l ) ; } int main () { while ( ~scanf ( "%d%d" , &n , &L ) && ( n || L ) ) solve () ; return 0 ; }