Submission #19007479

---

Source Code Expand

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

bool is_feasible(int N, int M, double r, vector<double> &r_vec,
        const vector<vector<double>> &dist)
{
    for (int i = N; i < N + M; ++i)
        r_vec.at(i) = r;
    for (int i = 0; i < N + M; ++i) {
        for (int j = i + 1; j < N + M; ++j) {
            if (r_vec.at(i) + r_vec.at(j) > dist[i][j])
                return false;
        }
    }
    return true;
}

int main()
{
    static const double inf = 1e+5;
    int N, M;
    cin >> N >> M;
    vector<int> x_vec(N + M), y_vec(N + M);
    vector<double> r_vec(N + M, inf);
    for (int i = 0; i < N; ++i)
        cin >> x_vec.at(i) >> y_vec.at(i) >> r_vec.at(i);
    for (int i = N; i < N + M; ++i)
        cin >> x_vec.at(i) >> y_vec.at(i);
    vector<vector<double>> dist(N + M, vector<double>(N + M, inf));
    for (int i = 0; i < N + M; ++i) {
        for (int j = i + 1; j < N + M; ++j) {
            int dx = x_vec.at(i) - x_vec.at(j);
            int dy = y_vec.at(i) - y_vec.at(j);
            dist[i][j] = hypot(dx, dy);
        }
    }
    double ok = 0;
    double ng = *min_element(r_vec.begin(), r_vec.end()) + 1e-6;
    while (abs(ok - ng) > 1e-6) {
        double mid = (ok + ng) / 2;
        if (is_feasible(N, M, mid, r_vec, dist))
            ok = mid;
        else
            ng = mid;
    }
    cout << setprecision(10) << ok << endl;
}

Submission Info

Judge Result