問題概要

二次元平面上に $N$ 個の円が与えられます。またそれらとは別に $M$ 個の点が与えられます。円同士は互いに交わることはなく、点が円に包含されることもありません。

今、 $M$ 個の点それぞれを中心とした円を描いています。ただし、そうしてできる $N+M$ 個の円のうち、どの 2 つも交差関係にも包含関係にもならないことはないようにします (外接するまでは許容します)。

このとき、 $N + M$ 個の円の半径の最小値として考えられる最大値を求めてください。

なお、許容誤差は $10^{-6}$ とします。

制約

$0 \le N, M \le 100$

最小値の最大化

今回の問題は「最小値の最大化」や「最大値の最小化」といえる枠組みになっています。そのような問題では、判定問題に帰着して二分探索に持ち込むことが有効です。今回は次のような問題を考えてみましょう。

$N + M$ 個の円の半径の最小値を $x$ 以上にすることは可能か？

この答えが Yes であるような $x$ の最大値が答えになります。そしてこの問題は次のように言い換えられます。一般に「最小値が $x$ 以上」は「すべて $x$ 以上」と言い換えられます。このような言い換えはとても重要な典型です。

$N + M$ 個の円の半径をすべて $x$ 以上にすることは可能か？

この判定問題を解いていきましょう。

判定問題

この判定問題を解くためには、実際に、

もともとの $N$ 個の円
新たに $M$ 個の点を中心とする半径 $x$ の円

を考えて、それら $N+M$ 個の円が互いに交差関係にも包含関係にもならないかどうかを確認すればよいでしょう (新たな円の半径を $x$ より大きくする必要はないことに注意しましょう)。

さて、一般に

中心が $(x_{1}, y_{1})$ 、半径が $r_{1}$ の円
中心が $(x_{2}, y_{2})$ 、半径が $r_{2}$ の円

が交差関係にも包含関係にもならないようにする条件を考えましょう。まず、2 つの円の中心間の距離を

$D = \sqrt((x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2})$

としましょう。このとき、条件は次のように記述できます。

$D \ge r_{1} + r_{2}$

この不等式がイコールになるとき、ちょうど 2 円が外接します。それよりも中心間距離 $D$ が大きくなると、2 円は離れていくことになります。

以上より、2 円が交差関係にも包含関係にもないための条件が求められました。よって $N+M$ 個の円から 2 つ選ぶすべての組合せに対して、交差関係にも包含関係にもないかどうかを判定していけばよいでしょう。

まとめ

判定問題にして二分探索に帰着します。判定問題は、 $O( (N + M)^{2} )$ の計算量で解けます。十分間に合います。

なお、もともとの円の半径の最小値よりも大きい答えにすることはできないことに注意しましょう。そこで以下のコードでは、もともとの円の半径の最小値を二分探索の区間の上側 right の初期値としています。

また、二分探索を用いずに解くこともできるようです。

コード

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

int main() {
    // 入力
    int N, M;
    cin >> N >> M;
    double mi = 10000;  // もともとの円の半径の最小値
    vector<double> x(N + M), y(N + M), r(N);
    for (int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i] >> r[i];
        mi = min(mi, r[i]);
    }
    for (int i = 0; i < M; ++i) cin >> x[i + N] >> y[i + N];

    // 二分探索の判定
    auto check = [&](double d) -> bool {
        for (int i = 0; i < N + M; ++i) {
            for (int j = i + 1; j < N + M; ++j) {
                double D = sqrt((x[i] - x[j]) * (x[i] - x[j])
                                + (y[i] - y[j]) * (y[i] - y[j]));
                double r1 = (i < N ? r[i] : d);
                double r2 = (j < N ? r[j] : d);
                if (D < r1 + r2) return false;
            }
        }
        return true;
    };

    // 二分探索
    double left = 0, right = mi;
    for (int _ = 0; _ < 100; ++_) {
        double mid = (left + right) / 2;
        if (check(mid)) left = mid;
        else right = mid;
    }

    cout << fixed << setprecision(10) << left << endl;
}