作者采用二分答案与并查集做法

#include "bits/stdc++.h"
#define pii pair<int,int>
#define pie acos(-1)
#define inf 0x7fffffff
#define IM INT_MAX
#define LM LONG_MAX
#define loo(i,l,r) for(int i=l;i<=r;i++)
#define ool(i,r,l) for(int i=r;i>=l;i--)
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
using namespace std;

const int N = 2e3+5;
const double eps = 1e-3;
int fa[N],n,k,idx;
double l = 0.0,r = inf*1.0;
map<pii,int> mp;
map<int,pii> pm;

int find(int x){
	if(fa[x] == x)return x;
	return fa[x] = find(fa[x]);
}

void unset(int x,int y){
	fa[find(x)] = find(y);
}

double dis(pii x,pii y){
	double disx = (x.first-y.first)*(x.first-y.first);
	double disy = (x.second-y.second)*(x.second-y.second);
	return sqrt(disx+disy);
}

bool check(double mid){
	int cnt = 0;
	loo(i,1,n)fa[i] = i;
	loo(x,1,n){
		loo(y,x,n){
			pii px = pm[x],py = pm[y];
			if(dis(px,py) <= mid && find(x)!=find(y))unset(x,y);
		}
	}
	loo(i,1,n)if(fa[i] == i)cnt++;
	return cnt >= k;
}

int main(){
	FASTIO
	scanf("%d%d",&n,&k);
	loo(i,1,n){
		int x,y;scanf("%d%d",&x,&y);
		pii t = make_pair(x,y);
		if(!mp[t])mp[t] = ++idx,pm[idx] = t;
	}
	while(r-l > eps){
		double mid = (l+r)/2;
		if(check(mid))l = mid;
		else r = mid;
	}
	printf("%.2lf\n",r);
	return 0;
}

有个疑问，$n = 1e3$ 时 $O(n^2logn)$ 在 $1s$ 内能过吗？