Quiz
https://atcoder.jp/contests/abc151/tasks/abc151_f
参考
- https://codeforces.com/blog/entry/23554
- 最小包含円・最小包含球
内容
- 中心を平均などで適当に決め、一番遠い点の方に少し近づける調整を繰り返す
- 計算量 O(N x R)
- R : 繰り返し回数(求められる精度によって調整?)
int n; double x[1005], y[1005], d, e; double dist(double a, double b) { return a * a + b * b; } int main() { scanf("%d", &n); // center double X = 0; double Y = 0; for (int i = 0; i < n; i++) { scanf("%lf%lf", &x[i], &y[i]); X += x[i]; Y += y[i]; } X /= n; Y /= n; double P = 0.1; // 収束するまで繰り返す for (int i = 0; i < 30000; i++) { // 中心と点0の距離 d = dist(X - x[0], Y - y[0]); int f = 0; // 中心と点0以外の距離 for (int j = 1; j < n; j++) { e = dist(X - x[j], Y - y[j]); // 中心から一番離れている点を探す if (d < e) { d = e; f = j; } } X += (x[f] - X) * P; Y += (y[f] - Y) * P; P *= 0.999; } cout << setprecision(20); p(sqrt(d)); // printf("%.3lf %.3lf\n%.3lf", X, Y, sqrt(d)); }
その他 O(N4)でたぶん解ける解法
- 「円は3点で決まる」と言われている
- 3点選んで、それに接する円を求め、その円が全ての点を含むか判定
- 全体の計算量 O(N4)