随机增量算法是计算几何的一个重要算法,它对理论知识要求不高,算法时间复杂度低,应用范围广大。
增量法 (Incremental Algorithm) 的思想与第一数学归纳法类似,它的本质是将一个问题化为规模刚好小一层的子问题。解决子问题后加入当前的对象。写成递归式是:
增量法形式简洁,可以应用于许多的几何题目中。
增量法往往结合随机化,可以避免最坏情况的出现。
在一个平面上有n个点,求一个半径最小的圆,能覆盖所有的点。
假设圆O是前i-1个点得最小覆盖圆,加入第i个点,如果在圆内或边上则什么也不做。否,新得到的最小覆盖圆肯定经过第i个点。
然后以第i个点为基础(半径为0),重复以上过程依次加入第j个点,若第j个点在圆外,则最小覆盖圆必经过第j个点。
重复以上步骤。(因为最多需要三个点来确定这个最小覆盖圆,所以重复三次)
遍历完所有点之后,所得到的圆就是覆盖所有点的最小圆。
时间复杂度
空间复杂度
题目描述
给出N个点,让你画一个最小的包含所有点的圆。
输入格式
先给出点的个数N,2<=N<=100000,再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)
输出格式
输出圆的半径,及圆心的坐标,保留10位小数
输入输出样例
输入
6
8.0 9.0
4.0 7.5
1.0 2.0
5.1 8.7
9.0 2.0
4.5 1.0
输出
5.0000000000
5.0000000000 5.0000000000
通过定理:如果点p不在集合S的最小覆盖圆内,则p一定在SU{p}的最小覆盖圆上。
根据这个定理,可以分三次确定前i个点的最小覆盖圆。
代码C++:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const db eps = 1e-8;
const db pi = acos(-1.0);
const ll maxn = 1e5 + 10;
inline int dcmp(db x) {
if(fabs(x) < eps) return 0;
return x > 0? 1: -1;
}
class Point {
public:
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
void input() {
scanf("%lf%lf", &x, &y);
}
bool operator<(const Point &a) const {
return (!dcmp(x - a.x))? dcmp(y - a.y) < 0: x < a.x;
}
bool operator==(const Point &a) const {
return dcmp(x - a.x) == 0 && dcmp(y - a.y) == 0;
}
db dis2(const Point a) {
return pow(x - a.x, 2) + pow(y - a.y, 2);
}
db dis(const Point a) {
return sqrt(dis2(a));
}
db dis2() {
return x * x + y * y;
}
db dis() {
return sqrt(dis2());
}
Point operator+(const Point a) {
return Point(x + a.x, y + a.y);
}
Point operator-(const Point a) {
return Point(x - a.x, y - a.y);
}
Point operator*(double p) {
return Point(x * p, y * p);
}
Point operator/(double p) {
return Point(x / p, y / p);
}
db dot(const Point a) {
return x * a.x + y * a.y;
}
db cross(const Point a) {
return x * a.y - y * a.x;
}
db ang(Point a) {
return acos((a.dis() * dis()) / dot(a));
}
};
typedef Point Vector;
class Circle {
public:
Point o;
db r;
Circle() {}
// 点和半径
Circle(Point o, db r):o(o), r(r){}
// 三点定圆
Circle(Point A, Point B, Point C) {
double a1 = B.x - A.x, b1 = B.y - A.y, c1 = (a1 * a1 + b1 * b1) / 2;
double a2 = C.x - A.x, b2 = C.y - A.y, c2 = (a2 * a2 + b2 * b2) / 2;
double d = a1 * b2 - a2 * b1;
o.x = A.x + (c1 * b2 - c2 * b1) / d;
o.y = A.y + (a1 * c2 - a2 * c1) / d;
r = o.dis(A);
}
Point point(db a) {
return Point(o.x + cos(a) * r, o.y + sin(a) * r);
}
// 点在圆内
bool PinC(Point p) {
db d = p.dis(o);
return dcmp(d - r) < 0;
}
// 点在圆外
bool PoutC(Point p) {
db d = p.dis(o);
return dcmp(d - r) > 0;
}
};
vector<Point> p;
// 最小圆覆盖
Circle min_circle(vector<Point> p) {
int sz = p.size();
// 随机点
random_shuffle(p.begin(), p.end());
Circle ans(p[0], 0.0);
for(int i = 0; i < sz; ++i) {
// 如果点在圆外,则用外面这个点作为新的半径
if(ans.PoutC(p[i])) {
ans = Circle(p[i], 0);
for(int j = 0; j < i; ++j) {
if(ans.PoutC(p[j])) {
// 找到2个点的圆
ans = Circle((p[i] + p[j]) / 2.0, p[i].dis(p[j]) / 2.0);
for(int k = 0; k < j; ++k) {
if(ans.PoutC(p[k])) {
// 找到3个点的圆
ans = Circle(p[i], p[j], p[k]);
}
}
}
}
}
}
return ans;
}
int main() {
int n;
scanf("%d", &n);
// 输入n个点
for(int i = 0; i < n; ++i) {
Point tmp;
tmp.input();
p.push_back(tmp);
}
// 通过点集计算最小的圆
Circle ans = min_circle(p);
printf("%.10lf\n%.10lf %.10lf\n", ans.r, ans.o.x, ans.o.y);
return 0;
}