0%

最小圆覆盖 - 随机增量法

最小圆覆盖板子。

题意

在一个平面上有 $n$ 个点,求一个半径最小的圆,能覆盖所有的点。

题解

OI Wiki

为什么是 $O(n)$ 的?

因为对于第 $i$ 个点,它在前 $i$ 个点形成的最小圆上的概率为 $\frac{3}{i}$。

如何求三个点形成的圆?

把三个点代入圆的方程,联立解出 $r$, $x_0$, $y_0$。

Code

抄 OI Wiki 的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 5;

int n;
double r;

struct Point
{
double x, y;
} p[N], o;

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

inline double dist(Point a, Point b)
{
return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

inline 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 (dist(o, p[i]) < r || cmp(dist(o, p[i]), r)) continue;
o.x = (p[i].x + p[1].x) / 2;
o.y = (p[i].y + p[1].y) / 2;
r = dist(p[i], p[1]) / 2;
for (int j = 2; j < i; j++)
{
if (dist(o, p[j]) < r || cmp(dist(o, p[j]), r)) continue;
o.x = (p[i].x + p[j].x) / 2;
o.y = (p[i].y + p[j].y) / 2;
r = dist(p[i], p[j]) / 2;
for (int k = 1; k < j; k++)
{
if (dist(o, p[k]) < r || cmp(dist(o, p[k]), r)) continue;
o = geto(p[i], p[j], p[k]);
r = dist(o, p[i]);
}
}
}
printf("%.10lf\n%.10lf %.10lf", r, o.x, o.y);
return 0;
}