BZOJ-1821: [JSOI2010]Group 部落划分

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1821

把所有点对按升序排序，然后用一个并查集一个一个加进去即可。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
 
using namespace std ;
 
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
 
const int maxn = 1010 ;
const int maxm = maxn * maxn ;
 
int father[ maxn ] , cnt ;
 
int Find( int x ) {
        int i , j , k ;
        for ( i = x ; father[ i ] ; i = father[ i ] ) ;
        for ( j = x ; father[ j ] ; k = father[ j ] , father[ j ] = i , j = k ) ;
        return i ;
}
 
struct point {
        int x , y ;
        int dist( point a ) {
               return ( x - a.x ) * ( x - a.x ) + ( y - a.y ) * ( y - a.y ) ;
        }
} p[ maxn ] ;
 
struct edge {
        int s , t , d ;
        void oper( int _s , int _t , int _d ) {
               s = _s , t = _t , d = _d ;
        }
        bool operator < ( const edge &a ) const {
               return d < a.d ;
        }
} e[ maxm ] ;
 
int n , m = 0 , k ;
 
int main(  ) {
        scanf( "%d%d" , &n , &k ) ;
        rep( i , n ) scanf( "%d%d" , &p[ i ].x , &p[ i ].y ) ;
        cnt = n ;
        rep( i , n ) for ( int j = i ; j ++ < n ; ) {
               e[ ++ m ].oper( i , j , p[ i ].dist( p[ j ] ) ) ;
        }
        sort( e + 1 , e + m + 1 ) ;
        rep( i , m ) {
               if ( Find( e[ i ].s ) != Find( e[ i ].t ) ) {
                       father[ Find( e[ i ].s ) ] = Find( e[ i ].t ) ;
                       if ( ( cnt -- ) <= k ) {
                               printf( "%.2f\n" , sqrt( e[ i ].d ) ) ;
                               return 0 ; 
                       }
               }
        }
        return 0 ; 
}