最小圆覆盖

前置知识：

二元一次方程求解

image-20240225095026280

通过经典的行列式知识可以知道

image-20240225095052186

不懂去学线性代数第一章行列式的第一小节，或者手动推导（）

三点定圆

如果能够有三个点，有两条垂直平分线可以求出圆心，再用圆心和一个点可以求出半径，这就是所谓的三点定圆。

算法：最小增量法

性质1：最小覆盖圆是唯一的
性质2：若圆O1是点集S的最小覆盖圆，则再新加一点p，他在集合S的外部，则新点集的最小覆盖圆一定过点p，即p一定在最小覆盖圆上。
性质3：最终的最小覆盖圆一定只有两种情况：1是圆上至少有三个点，由三点限制一个圆（三点共圆）；2是圆上只有两个点，则该圆一定是以该两点的连线为直径的。
性质3：最终的最小覆盖圆一定只有两种情况：1是圆上至少有三个点，由三点限制一个圆（三点共圆）；2是圆上只有两个点，则该圆一定是以该两点的连线为直径的。

都比较显而易见（）

随机增量法：就是从所有点里随机选一个加入自己的集合中，然后维护这个集合，然后再随机选一个点加入集合，再维护… 直到所有点都加入这个集合，那么最终的这个集合就是满足我要求的情况了。 然后我们找一个圆就是看能不能找到这个圆上的三个点。

首先我们先将所有点随机化。 三层循环，第一层从2到n循环i，我们将圆初始化为以第一个点为圆心，半径为0的圆。然后我们要循环判断i点在圆内还是在圆外，若在圆内（在圆上也认为是圆内），那Ci和Ci-1是相同的，我们直接循环i+1就行了；如果i在圆外，那么Ci一定过点i（性质2），然后我们就进第二层循环。 第二层从1到i-1循环j，我们将圆先初始化为以点i为圆心，0为半径的圆，然后不断去加点j，若j在圆内，就继续循环j+1；若j在圆外，就再进第三层循环。 第三层从1到j-1循环k，将圆先初始化为以i和j为直径的圆，然后再循环判断k，若在圆内，就继续循环下一个k+1；若k在圆外，就将圆更新为i、j、k三点确定的圆，直到最后求出来的圆就是最小覆盖圆。

最小圆覆盖

题目描述

给出 \(N\) 个点，让你画一个最小的包含所有点的圆。

输入格式

第一行一个整数 \(N\) 表示点的个数。

接下来 \(N\) 行每行两个实数 \(x_i,y_i\) 表示点的坐标。最多两位小数。

输出格式

第一行一个实数表示圆的半径。

第二行两个实数表示圆心的坐标。

本题开启 spj，您的答案与标准答案误差不超过 \(10^{-9}\) 时，视为正确。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
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

样例输出 #1

1
2
5.0000000000
5.0000000000 5.0000000000

提示

对于 \(100\%\) 的数据，\(1\leq N\leq 10^5\)，\(|x_i|,|y_i|\leq 10^4\)。

2022.2.26 添加 spj

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
const double eps = 1e-8,PI = acos(-1);	//会用到的常数
#define x first		//方便用pair
#define y second
typedef pair<double,double> PDD;
struct Circle{		//存圆
	PDD o;		//圆心o
	double r;	//半径r
}c;

PDD p[N];	//p来存点
int n;

PDD operator+(PDD a,PDD b)	//重在运算符+，方便pair运算
{
	return {a.x+b.x, a.y+b.y};
}

PDD operator-(PDD a,PDD b)//点的减法
{
	return {a.x-b.x, a.y-b.y};
}

double operator*(PDD a,PDD b)	//叉乘
{
	return a.x*b.y - a.y*b.x;	//x1*y2 - x2*y1
}

PDD operator*(PDD a,double b)	//数乘
{
	return {a.x*b, a.y*b};
}

PDD operator/(PDD a,double b)
{
	return {a.x/b, a.y/b};
}

int judge(double a,double b)	//两个double数比大小，相等返回0，小于返回-1，大于返回1
{
	if(fabs(a-b) < eps)
		return 0;
	if(a < b)
		return -1;
	return 1;
}

PDD rotate(PDD a,double b)	//向量a旋转b°后的向量
{
	return {a.x*cos(b)+a.y*sin(b), -a.x*sin(b)+a.y*cos(b)};
}

double lens(PDD a,PDD b)	//求两点距离
{
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx*dx + dy*dy);	//根号下x方加y方
}

PDD intersection(PDD p,PDD v,PDD q,PDD w)	//求两直线交点
{
	PDD u = p - q;
	double t = w*u / (v*w);
	return p + v*t;
}

pair<PDD,PDD> bisector(PDD a,PDD b)	//求两点中垂线
{
	PDD p = (a+b) / 2;	//先求出a和b连线的中点，就是横纵坐标和的一半
	PDD v = rotate(b-a,PI/2);	//然后求ab向量旋转90°的向量
	return {p,v};		//就有了直线上一点p和一个向量v，根据点向式可以写出一条直线方程
}

Circle circle(PDD a,PDD b,PDD c)	//已知三点，求外接圆
{
	auto n = bisector(a,b),m = bisector(a,c);	//先求出两个边的中垂线
	PDD o = intersection(n.x,n.y,m.x,m.y);	//然后求两中垂线交点就是圆心o
	double r = lens(o,a);	//求出oa长度就是半径
	return {o,r};		//返回圆心和半径
}

int main()
{
	cin >> n;
	for(int i = 0;i < n;i++)
		cin >> p[i].x >> p[i].y;	//输入个点
	random_shuffle(p,p+n);		//随机化p
	c = {p[0],0};			//初始化圆为p[0]
	for(int i = 1;i < n;i++)	//第一次循环
	{
		if(judge(c.r,lens(c.o,p[i])) == -1)	//如果p[i]在圆外
		{
			c = {p[i],0};			//初始化圆为p[i]
			for(int j = 0;j < i;j++)	//第二层循环
			{
				if(judge(c.r,lens(c.o,p[j])) == -1)	//如果p[j]在圆外
				{
					c = {(p[i]+p[j])/2,lens(p[i],p[j])/2};	//初始化圆为p[i]和p[j]为直径的圆
					for(int k = 0;k < j;k++)	//第三层循环
					{
						if(judge(c.r,lens(c.o,p[k])) == -1)	//如果p[k]在圆外
							c = circle(p[i],p[j],p[k]);		//i、j、k三点求一个唯一的圆
					}
				}
			}
		}
	}
	printf("%.10lf\n",c.r);		//输出圆半径
	printf("%.10lf %.10lf\n",c.o.x,c.o.y);	//输出圆心坐标

	return 0;
}