题解 | #信号覆盖#

并查表

#include <bits/stdc++.h>
#include <cmath>
#include <vector>
using namespace std;

struct Node{
    int u;
    int v;
    int dis;
    Node(int x, int y, int dis):u(x), v(y), dis(dis){};
    bool operator <(Node n){
        return dis<n.dis;
    }
};

int getDis(vector<int> pos1, vector<int> pos2){
    return pow(abs(pos1[0]-pos2[0]),2)+pow(abs(pos1[1]-pos2[1]), 2);
}

int find(vector<int>& father, int x){
    if(father[x] == x) return x;
    return father[x] = find(father, father[x]);
}

int unite(vector<int>& father, vector<int>&size, int u, int v){
    int f1 = find(father, u);
    int f2 = find(father, v);
    if(f1==f2) return size[f2];
    father[f1] = f2;
    size[f2] += size[f1];
    return size[f2];
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> dis(n, vector<int>(n));
    vector<vector<int>> pos(n, vector<int>(2));
    for(int i=0;i<n;i++){
        cin >> pos[i][0] >> pos[i][1];
    }
    vector<Node> dist;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist.emplace_back(i, j, getDis(pos[i], pos[j]));
        }
    }
    sort(dist.begin(), dist.end());
    if(k==1){
        cout << 0 << endl;
        return 0;
    }
    vector<int> parent(n);
    for(int i=0;i<n;i++) parent[i] = i;
    vector<int> size(n,1);
    for(Node node : dist){
        int cur_size = unite(parent, size, node.u, node.v);
        if(cur_size >= k){
            cout << node.dis << endl;
            return 0;
        }
    }
}
// 64 位输出请用 printf("%lld")