Enclose All [AtCoder Beginner Contest 151 F]

https://atcoder.jp/contests/abc151/tasks/abc151_f

前提知識

• 幾何

解説

https://atcoder.jp/contests/abc151/submissions/9483086

「最小包含円」という有名問題がある。
これと同義の問題であるが、これのよく知られている解法はガチ解法なので、もっと分かりやすい方を説明する。

自分は、ここでICPCの対策をしていたので、解法はすぐに思いついた（幾何特集の1番目の問題）。
これがない場合はどうやって思いつくかであるが、こういう選択肢が膨大にあるような問題ではある程度の仮定がないと話が進まないことがある。
今回でいうと、最適解は3点以上の点の上にあるとか、そういう仮定。

今回の問題の解法は「ある2点を結んだ線分を直径として持つ円、もしくは、ある3点を通る円のいずれかが半径最小の円となるので、全列挙」である。
解法自体は簡単だが、幾何ライブラリを持っている必要がある。
もし大学生以下でICPCに出る予定があるなら、整備しておく価値はあるだろう。

必要な要素としては、
- 2点間の距離
- 2点間の中点
- 3点を通る円の中心
があれば、解くことができる。
3番目が一番難しいと思うが、これは3点をつないでできる三角形の外心である。
2点ずつで垂直二等分線を求めて、交点を求めてもいいし、まあ、色々頑張る。
自分は、実装まで覚えていない（というかわかってないやつもあるかも）
頑張ってとしか…

あと、大小関係を比較するときにEPSを使った誤差軽減をする必要もある。
「幾何 誤差 EPS」みたいな感じにググると情報が出てくるが、自分は以下のように運用している。
小数の比較をするときに以下のように変換して使う誤差軽減法である。

const double EPS = 1e-8;
if(a <= b + EPS) // a <= b
if(a < b - EPS) // a < b
if(abs(a - b) < EPS) // a == b

EPSを調整しないと通らない問題もあったりするが、最近は見かけていないので、もう無くなったのかな？

int N;
P ps[50];
//---------------------------------------------------------------------------------------------------
bool check(P cent, double rad) {
    rep(i, 0, N) {
        double d = abs(ps[i] - cent);
        if (rad < d - EPS) return false;
    }
    return true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        ps[i] = P(x, y);
    }

    double ans = inf;
    rep(a, 0, N) rep(b, a + 1, N) {
        P cent = (ps[a] + ps[b]) / 2;
        double rad = abs(ps[a] - cent);
        if (check(cent, rad)) chmin(ans, rad);
    }
    rep(a, 0, N) rep(b, a + 1, N) rep(c, b + 1, N) if (!onSameLine(ps[a], ps[b], ps[c])) {
        P cent = three_P_circle(ps[a], ps[b], ps[c]);
        double rad = abs(ps[a] - cent);
        if (check(cent, rad)) chmin(ans, rad);
    }
    printf("%.18f\n", ans);
}