洛谷P1742 最小圆覆盖(计算几何)

题意

题目链接

Sol

暴力做法是\(O(n^3)\)枚举三个点然后check一下是否能包含所有点

考虑一种随机算法，首先把序列random_shuffle一下。

然后我们枚举一个点\(i\)，并维护一个当前的圆。

再枚举一个点\(j\)，如果该点在圆内继续，否则用\(i, j\)构造出的圆替换出之前的圆。

再枚举一个点\(k\)，如果该点在圆内继续，否则用\(i, j, k\)构造出一个新的圆。

这样的期望复杂度是O(n)的(不会证)

一开始我以为这样做的正确性有点问题，也就是说可能找到一个不优的解。但是显然是不对的，因为如果有更优的解且面积比当前小的话，这个解最起码要包含当前的不优解的三个点，是矛盾的。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;

int N;

double R;

struct Point {

	double x, y;

}p[MAXN], C;

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));

}

void MakeC(Point p1, Point p2, Point p3) {

	double a = p2.x - p1.x,

		   b = p2.y - p1.y,

		   c = p3.x - p1.x,

		   d = p3.y - p1.y,

		   e = (sqr(p2.x) - sqr(p1.x) + sqr(p2.y) - sqr(p1.y)) / 2,

		   f = (sqr(p3.x) - sqr(p1.x) + sqr(p3.y) - sqr(p1.y)) / 2;

	C.x = (e * d - b * f) / (a * d - b * c);

	C.y = (a * f - e * c) / (a * d - b * c);

	R = dis(C, p1);

}

int main() {

	cin >> N;

	for(int i = 1; i <= N; i++) scanf("%lf %lf", &p[i].x, &p[i].y);

	random_shuffle(p + 1, p + N + 1);

	for(int i = 1; i <= N; i++) {

		if(dis(p[i], C) < R) continue;

		C = p[i]; R = 0;

		for(int j = 1; j <= i - 1; j++) {

			if(dis(p[j], C) < R) continue;

			C.x = (p[i].x + p[j].x) / 2.0;

			C.y = (p[i].y + p[j].y) / 2.0;

			R = dis(C, p[j]);

			for(int k = 1; k <= j - 1; k++) {

				if(dis(p[k], C) < R) continue;

				MakeC(p[i], p[j], p[k]);

			}

		}

	}

	printf("%.10lf\n", R);

	printf("%.10lf %.10lf", C.x, C.y);

	return 0;

}