题解 | 信号覆盖

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 1e6; // 根据实际问题调整大小


int n, k;
int father[MAXN];
int num[MAXN];
pair<int, int> pos[MAXN];
vector<pair<pair<int, int>, int>> edges; // 明确定义 edges 的类型

int get_f(int x) {
    if (father[x] == x) return x;
    father[x] = get_f(father[x]);
    return father[x];
}

int get_num(int x) {
    x = get_f(x);
    return num[x];
}

void merge(int x, int y) {
    x = get_f(x);
    y = get_f(y);
    if (x == y) return;
    father[x] = y;
    num[y] += num[x];
}

int solve(int w) {
    int l = 0, r = w;
    while (l < r) {
        int mid = l + (r - l) / 2;
        for (int i = 1; i <= n; i++) {
            father[i] = i;
            num[i] = 1;
        }
        for (auto& e : edges) {
            if (e.second <= mid) {
                merge(e.first.first, e.first.second);
            }
        }
        int max_num = 0;
        for (int i = 1; i <= n; i++) {
            max_num = max(max_num, get_num(i));
        }
        if (max_num >= k) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> pos[i].first >> pos[i].second;
    }
    int w = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            int d = (pos[i].first - pos[j].first) * (pos[i].first - pos[j].first) +
                    (pos[i].second - pos[j].second) * (pos[i].second - pos[j].second);
            edges.push_back({{i, j}, d}); // 明确使用 pair 的初始化
            w = max(w, d);
        }
    }
    cout << solve(w) << endl;
    return 0;
}