题解 | #信号覆盖#

#include<bits/stdc++.h> 

using namespace std;

vector<int> xarr,yarr;

struct Node{
    int u,v; // 点！
    int dis;
    Node(int _u,int _v,int _dis):u(_u),v(_v),dis(_dis){}
    
    bool operator <(const Node& node){
        return dis < node.dis;
    }
    
} ;


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


int distance(int u,int v){
    int xx = xarr[u] - xarr[v];
    int yy = yarr[u] - yarr[v];
    return xx*xx + yy*yy;
}

int main(){
    int n,k;
    cin >> n >> k;
    xarr.resize(n); yarr.resize(n);
    
    
    for(int i = 0; i < n; i++){
        cin >> xarr[i] >> yarr[i];
    }
    
    vector<Node> arr;
    
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            arr.emplace_back(Node(i,j,distance(i,j)));
        }
    }
    
    sort(arr.begin(),arr.end());
    
    if(k == 1){
        cout << 0 << endl;
        return 0;
    }
    
    vector<int> father(n);
    
    for(int i = 0; i < n; i++) father[i] = i;
    
    vector<int> size(n,1);
    
    for(Node node : arr){
        int f1 = find(father,node.u);
        int f2 = find(father,node.v);
        
        if(f1 != f2){
            father[f1] = f2;
            size[f2] += size[f1];
            if(size[f2] >= k){
                cout << node.dis << endl;
                return 0;
            }
        }
       
    }
    assert(0);
    return 0;
}