二分答案 + 最小生成树 + 并查集判定 + 精度trick
# include<iostream>
# include<cstring>
# include<algorithm>
# include<vector>
# include<cmath>
using namespace std;
typedef pair<int, int> PII;
// 所有点连接 可以视为生成树模型
const int N = 510;
const double esp = 1e-6;
int T;
int n,m;
bool st[N];
PII nodes[N];
int p[N];
struct edge{
int l,r;
double w;
bool operator<(edge& e1){
return w < e1.w;
}
};
vector<edge> edges;
int find(int x){
if(p[x] != x){
p[x] = find(p[x]);
}
return p[x];
}
bool check(double x){
// 跑一遍krustral
memset(st, 0, sizeof st);
for(int i=1;i<=m;++i) p[i] = i;
for(int i=0;i<edges.size();++i){
int a = edges[i].l,b = edges[i].r,w = edges[i].w;
int fa = find(a),fb = find(b);
if(fa != fb){
if(w <= x){
p[fa] = fb;
}else{
break; // 边的按照从小到大排列的 因此此时可以直接退出了
}
}
}
// 找连通分量的个数 一个连通分量中只需要放置一个即可 并且s>=1所以不需要加特判了
int cnt = 0;
for(int i=1;i<=m;++i){
if(find(i) == i){
cnt ++;
}
}
return cnt <= n;
}
// 直接采用d**2 距离的平方进行二分比较 防止精度问题
double get_dist(PII& p1,PII& p2){
double dx = p1.first - p2.first;
double dy = p1.second - p2.second;
return dx * dx + dy * dy;
}
int main(){
cin >> T;
while(T--){
cin >> n >> m;
double maxv = 0.0;
for(int i=1;i<=m;++i){
int x,y;
cin >> x >> y;
nodes[i] = {x,y};
}
edges.clear();
for(int i=1;i<=m;++i){
for(int j=i+1;j<=m;++j){
double d = get_dist(nodes[i],nodes[j]);
maxv = max(maxv,d);
edges.push_back({i,j,d});
}
}
// 对于边进行排序
sort(edges.begin(),edges.end());
// 合理分配n个卫星 使得所有点可以连通 并且D最小
// 具有二段性 二分D的数值
double l = 0.0,r = maxv;
while(l + esp < r){
double mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid;
}
printf("%.2f\n",sqrt(l));
}
return 0;
}