最小圆覆盖

还是一个计算几何。

1. 性质

1）唯一性

明显，如果我们能找到两个圆的话，他们的交也一定是可以的。我们可以尝试构造以相交的弦为直径构造一个圆，很明显会更小。

2）

如果 $P$ 不在集合 $S$ 的最小覆盖圆的内部，则 $P$ 在 $\{P\}\cup S$ 的最小覆盖圆的边上。

首先，一个最小覆盖圆肯定会经过集合内的至少三个点。（在集合点数 $\geq 3$ 的时候）

反证：假设 $P$ 不在 $\{P\}\cup S$ 的最小覆盖圆的边上，那么 $\{P\}\cup S$ 的最小覆盖圆就是 $S$ 的最小覆盖圆。

但是 $S$ 的最小覆盖圆是无法覆盖到 $P$ 的，所以就会导致 $\{P\}\cup S$ 的最小圆覆盖无法覆盖到 $P$，矛盾，故原命题成立。

2. 算法流程

首先随机化，防止复杂度退化。

接着，我们将圆设置为 $(p(1), 0)$，表示圆心和半径。

然后，我们枚举每一个点，如果当前点 $p(i)$ 不在最小覆盖圆里的话，那么，我们由前面的性质得到，$p(i)$ 一定在 $\{1, …, i\}$ 的最小圆覆盖的边上。

现在，我们将圆设置为 $(p(i), 0)$，然后再暴力枚举前面的点。

如果如果 $p(j)$ 不在圆内的话，那么 $p(j)$ 在 $\{1, …, j\}\cup\{i\}$ 的最小圆覆盖的边上。同时，由于 $p(i)$ 不在 $\{1, …, i - 1\}$ 的最小圆覆盖里，那么一定导致 $p(i)$ 不在 $\{1, …, j\}$ 的最小覆盖圆上。

那么，我们就可以得到，$p(i), p(j)$ 都在 $\{1, …, j\}\cup \{i\}$ 的圆的边上。

因为找一个圆需要 $3$ 个点才能确定，所以我们再去寻找一个点。

我们将圆设置为 $p(i), p(j)$ 为直径的圆，再从前循环 $p(k)$，寻找到 $p(k)$ 不在 $p(i), p(j)$ 为直径的圆上。仿照前面的证明，我们就可以得到 $p(k), p(i), p(j)$ 都在圆上，我们就是求出了 $\{1, …, k\} \cup\{i, j\}$ 的最小圆覆盖。

最后我们一直循环，直到最后覆盖到了 $\{1, …, i - 1\}\cup\{i\}$ 也就是 $\{1, …, i\}$ 的圆覆盖。

3. 复杂度

看似有 $O(n ^ 3)$，但是两步判断都是 $\dfrac{3}{n}$ 的概率，我们就可以得到时间复杂度为 $O(n)$。（感觉特别玄学

Point get_point(Point p1, Point k1, Point p2, Point k2){
	Point u = p1 - p2;
	double t = (k2 * u) / (k1 * k2);
	return p1 + k1 * t;
}

Circle circle_by_point(Point a, Point b, Point c){
	auto l1 = get_line(a, b), l2 = get_line(a, c);
	Point o = get_point(l1.first, l1.second, l2.first, l2.second);
	return {o, dist2(a, o)};
}

Circle min_circle(Point *p, int n)
{
	random_shuffle(p + 1, p + n + 1);
	Circle ans = {p[1], 0};
	for (int i = 2; i <= n; ++ i)
	{
		if (in_circle(ans, p[i])) continue;
		ans = {p[i], 0};
		for (int j = 1; j < i; ++ j){
			if (in_circle(ans, p[j])) continue;
			ans = {(p[i] + p[j]) / 2, dist2((p[i] + p[j]) / 2, p[i])};
			for (int k = 1; k < j; ++ k)
				if (!in_circle(ans, p[k])) ans = circle_by_point(p[i], p[j], p[k]);
		}
	}
	ans.r = sqrt(ans.r);
	return ans;
}