# A Simple Task of Kruskal's

Problem:
Given N, N points on a 2D plane, and a value K, find the maximum D such that all points can be distributed into K non-empty subsets, where D is the minimum distance between any pair of points not in the same subset.
Analysis:
Construct a minimum span tree with Kruskal's. Then, to split into K non-empty subsets is essentially to bring away ( N - K ) edges from the span tree. Now it is clear that we will take away the minimum edges in the first ( N - K ) by the rule of Greedy.

```typedef vector< int > vi;
typedef vector< double > vd;
typedef pair< int, int > pii;
typedef vector< pii > vp;
typedef pair< double, pii > pdp;
typedef vector< pdp > vdp;

double edis( pii a, pii b ){
double dx = a.first - b.first;
double dy = a.second - b.second;
return sqrt( dx * dx + dy * dy );
}

struct UnionFind{
vi fa;
UnionFind( int sz ){
fa.resize( sz );
for( int i = 0; i < sz; ++i )
fa[ i ] = i;
}
int find( int x ){
if( fa[ x ] == x ) return x;
return fa[ x ] = find( fa[ x ] );
}
bool unite( int a, int b ){
int x = find( a );
int y = find( b );
if( x == y ) return false;
fa[ x ] = y; return true;
}
};

struct Kruskal{ // minimum span tree
int n;
vdp edge;
vd chose_val;
Kruskal( const int _n, const vdp &_e ) : n( _n ), edge( _e ){}
vd solve(){
UnionFind *uf = new UnionFind( n );
for( int i = 0; i < edge.size(); ++i ){
double d = edge[ i ].first;
int u = edge[ i ].second.first;
int v = edge[ i ].second.second;
if( uf->unite( u, v ) )
chose_val.push_back( d );
}
return chose_val;
}
};

void solve(){
int N; cin >> N;
vp P( N );
for( int i = 0; i < N; ++i )
cin >> P[ i ].first >> P[ i ].second;
int K; cin >> K;
vdp edge;
for( int i = 0; i < N; ++i )
for( int j = i + 1; j < N; ++j )
edge.push_back( pdp( edis( P[ i ], P[ j ] ), pii( i, j ) ) );
sort( edge.begin(), edge.end() );
Kruskal *krus = new Kruskal( N, edge );
cout << fixed << setprecision( 9 ) << krus->solve()[ N - K ] << endl;
}
```