题目链接：https://www.luogu.com.cn/problem/P4047
感受：比赛时秒认为是二分，但二分的细节很多且不好处理，但我就是要二分。
主要死在对并查集还不够熟悉，本题二分判断有几个部落只能通过并查集来实现，普通的模拟无法实现。
思路：对答案进行二分，当算出来的联通的数目大于题目给定的，说明二分的答案偏小。反之答案偏大。
这里说一下当两点间的距离与二分的答案相等的情况，如本题样例，当二分答案为0.9999时，联通块数目是4，当二分答案为1时，连通块数目是1，并没有二分到k，我们只需要去掉二分答案为1时的边的长度为1的边，这样联通块的数目就与题目给定的相等了。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef pair<int,int>P;
int p[N];
P edge[N];
int n,k;
int find(int x){
if (x!=p[x]) p[x] = find(p[x]);
return p[x];
}
double get(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
bool check(double mid){
int cnt = 0;
for (int i=1;i<=n;i++) p[i] = i;
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++){
double d = get(edge[i].first,edge[i].second,edge[j].first,edge[j].second);
if (d<=mid){
int X = find(i),Y = find(j);
p[X] = Y;
}
}
}
for (int i=1;i<=n;i++){
if (p[i]==i) cnt++;
}
if (cnt>=k) return 1;
return 0;
}
int main(){
cin>>n>>k;
for (int i=1;i<=n;i++) cin>>edge[i].first>>edge[i].second;
double l = 0,r = 20000;
while(r-l>1e-9){
double mid = (l+r)/2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2f",l);
return 0;
}