\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
解法
最小包含円を求めるアルゴリズムが知られている． 下に凸な関数に対して三分探索を二回用いる．
\(P := {P_{i}}_{i \in N}\) を平面の点の集合とする． \(f_{P}(x,y) := \) 点 \(\ (x,y)\ \) から\(P\) の距離への最大値とする． すなわち，
\(f_{P}(x,y) := max_{i \in N} \ dist*1;
};
// f: 下に凸
// rem: 三分探索なので，分母は 3.
// rem: 三分探索なので，区間の幅が 2/3倍になる．
// 0.66 ^80 < 3.661e-15
auto tri = [](auto f) -> double {
double l = 0, r = 2005;
rep(i,80){
double cl = (l*2 + r) / 3.;
double cr = (l + r*2) / 3.;
if(f(cl) < f(cr)) r = cr; // not f(cl) < cr
else l = cl;
}
return f(l);
};
auto f = [=](double x, double y) -> double {
double ret = -1;
rep(i,n){
double d = dis(x,y, p[i].first, p[i].second);
chmax(ret, d);
}
return ret;
};
auto g = [=](double x) -> double {
return tri( [&](double y){return f(x,y);} );
};
printf("%.10lf\n", tri(g));
return 0;
}
