题解 | #信号覆盖#

解题思路：二分+并查集

时间复杂度：O(n^2 * log(x^2+y^2))

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3+100;

int n,k;
int fa[MAXN];  //并查集，记录当前节点的父节点，初始化fa[i] = i;
int d[MAXN][MAXN]; //记录距离
pair<int,int>pos[MAXN]; //记录坐标
int num[MAXN]; // 记录每个集合的数量，初始化均为1

int get_fa(int x){ //获得集合的root
    if(fa[x]==x)return x;
    return fa[x] = get_fa(fa[x]);
}
int get_num(int x){ //获得数量
    x = get_fa(x);
    return num[x];
}
void merge(int x, int y){ //合并两个集合
    x = get_fa(x);
    y = get_fa(y);
    if(x==y)return;
    fa[x] = y;
    num[y]+=num[x];
}
int solve(int ma){ //二分找答案
    int r = ma;
    int l = 0;
    while(l<r){
        int max_num=0;
        for(int i=1;i<=n;++i){  //初始化fa数组和num数组
            fa[i] = i;
            num[i] = 1;
        }
        int mid = (l+r)/2;  
        for(int i=1;i<=n;++i){ //把所有能通信的merge一块儿
            for(int j=1;j<i;++j){
                if(d[i][j]<=mid)merge(i,j); //merge中更新num和fa
            }
        }
        for(int i=1;i<=n;++i){// 查找最大的集合
            max_num = max(max_num, get_num(i));
        }
        if(max_num>=k)r=mid;//如果最大的集合大于k，说明还可以缩小
        else l=mid+1; //小于k，则不能再缩小了
    }
    return l;
}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&pos[i].first, &pos[i].second);
    int ma = 0;
    for(int i=1;i<=n;++i){ //更新距离
        for(int j=1;j<=n;++j){
            d[i][j] = (pos[i].first-pos[j].first)*(pos[i].first-pos[j].first);
            d[i][j]+=(pos[i].second-pos[j].second)*(pos[i].second-pos[j].second);
            ma = max(ma,d[i][j]); //记录最大值，最大值的时候所有都互相连接
        }
    }
    printf("%d\n",solve(ma));
    
}