perogram

F - Enclose All 参考リンクのみ cpp c++

Quiz

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

参考

内容

  • 中心を平均などで適当に決め、一番遠い点の方に少し近づける調整を繰り返す
  • 計算量 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)でたぶん解ける解法