A1209 [HSPC2023] 信号干扰仪

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

// 信号干扰仪（A1209，HSPC2023）
//
// 每台仪器的半径随时间线性增长；一旦它的边界与另一台仪器的边界相切，就停止增长。
// 用事件模拟：每对仪器都有一个「边界相切」的时刻，每次取全局最早的那个事件处理。
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<double> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

    // 两台仪器之间的距离
    vector<vector<double>> d(n, vector<double>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            d[i][j] = d[j][i] = hypot(x[i] - x[j], y[i] - y[j]);
        }
    }

    vector<double> r(n, 0);        // 最终半径
    vector<bool> frozen(n, false); // 是否已经停止增长

    for (int step = 0; step < n; step++) {
        double best = 1e100;       // 下一个接触事件的时刻
        int fi = -1, fj = -1;      // fi：还在长的仪器；fj：与它接触的另一台
        for (int i = 0; i < n; i++) {
            if (frozen[i]) continue;
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
                double t;
                if (frozen[j]) {
                    t = d[i][j] - r[j]; // j 已停止，i 长到边界碰到它
                } else {
                    t = d[i][j] / 2.0;  // 两台都在长，边界外切
                }
                if (t < best) { best = t; fi = i; fj = j; }
            }
        }
        if (fi == -1) break; // 全部停止
        r[fi] = best;
        frozen[fi] = true;
        if (!frozen[fj]) { // 两台都在长时互相接触，两台都停止
            r[fj] = best;
            frozen[fj] = true;
        }
    }

    for (int i = 0; i < n; i++) printf("%.2f\n", r[i]);
    return 0;
}