AIOJ

The randomized incremental algorithm is an important computational-geometry algorithm. It requires little theoretical knowledge, has low time complexity, and applies to a wide range of problems.

Introduction

The idea of the incremental algorithm is similar to ordinary mathematical induction: reduce a problem to a subproblem that is exactly one level smaller, solve the subproblem, and then add the current object. Its recurrence is

T(n)=T(n-1)+g(n)

The incremental method has a concise form and can be applied to many geometry problems.

The incremental method is often combined with randomization to avoid the worst case.

Minimum enclosing circle

Problem statement

Given $n$ points on a plane, find the circle with minimum radius that covers all of them.

Process

Suppose circle $O$ is the minimum enclosing circle of the first $i-1$ points. Add the $i$ -th point. If it lies inside or on the circle, do nothing. Otherwise, the new minimum enclosing circle must pass through the $i$ -th point.

Then take the $i$ -th point as the basis (with radius $0$ ), and repeat the above process while adding the points $j$ one by one. If point $j$ lies outside the circle, the minimum enclosing circle must pass through point $j$ .

Repeat the above steps. (At most three points are needed to determine this minimum enclosing circle, so the process is nested three times.)

After all points have been traversed, the resulting circle is the minimum circle covering all points.

Properties

Time complexity: $O(n)$ ; see the references for a proof.

Space complexity: $O(n)$

Implementation

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

int n;
double r;

struct point {
  double x, y;
} p[100005], o;

double sqr(double x) { return x * x; }

double dis(point a, point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }

bool cmp(double a, double b) { return fabs(a - b) < 1e-8; }

point geto(point a, point b, point c) {
  double a1, a2, b1, b2, c1, c2;
  point ans;
  a1 = 2 * (b.x - a.x), b1 = 2 * (b.y - a.y),
  c1 = sqr(b.x) - sqr(a.x) + sqr(b.y) - sqr(a.y);
  a2 = 2 * (c.x - a.x), b2 = 2 * (c.y - a.y),
  c2 = sqr(c.x) - sqr(a.x) + sqr(c.y) - sqr(a.y);
  if (cmp(a1, 0)) {
    ans.y = c1 / b1;
    ans.x = (c2 - ans.y * b2) / a2;
  } else if (cmp(b1, 0)) {
    ans.x = c1 / a1;
    ans.y = (c2 - ans.x * a2) / b2;
  } else {
    ans.x = (c2 * b1 - c1 * b2) / (a2 * b1 - a1 * b2);
    ans.y = (c2 * a1 - c1 * a2) / (b2 * a1 - b1 * a2);
  }
  return ans;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
  for (int i = 1; i <= n; i++) swap(p[rand() % n + 1], p[rand() % n + 1]);
  o = p[1];
  for (int i = 1; i <= n; i++) {
    if (dis(o, p[i]) < r || cmp(dis(o, p[i]), r)) continue;
    o.x = (p[i].x + p[1].x) / 2;
    o.y = (p[i].y + p[1].y) / 2;
    r = dis(p[i], p[1]) / 2;
    for (int j = 2; j < i; j++) {
      if (dis(o, p[j]) < r || cmp(dis(o, p[j]), r)) continue;
      o.x = (p[i].x + p[j].x) / 2;
      o.y = (p[i].y + p[j].y) / 2;
      r = dis(p[i], p[j]) / 2;
      for (int k = 1; k < j; k++) {
        if (dis(o, p[k]) < r || cmp(dis(o, p[k]), r)) continue;
        o = geto(p[i], p[j], p[k]);
        r = dis(o, p[i]);
      }
    }
  }
  printf("%.10lf\n%.10lf %.10lf", r, o.x, o.y);
  return 0;
}