最小圆覆盖

题目描述

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

输入格式
先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)

输出格式
输出圆的半径，及圆心的坐标，保留10位小数

输入输出样例
输入 #1复制
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复制
5.0000000000
5.0000000000 5.0000000000

说明/提示
5.00 5.00 5.0

随机增量法：

我们先把所有点随机化（这点很重要）。

然后从第一个点开始判断，如果该点在圆的内部，直接忽略。否则以该点为圆心，半径为0找新的圆。

然后找到第二个在圆外的点，新的圆点就是两点的中点，半径也可求出。然后找第三个在圆外的点，之后根据三点定圆。然后一直反复即可。

三点定圆，通过圆心到三点的距离即可推出。

推荐博客：三点定圆的求法

然后这样看似是 n^3的复杂度，但是其实是 O(n)的复杂度，证明比较繁琐（我也不会）。

大概就是：当点完全随机时，第i个点在前i-1个点的最小覆盖圆外的几率是3/i

(学什么，什么不考。只有多学点咯！！！)

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n;
double r;
struct node{double x,y;}t[N],res;
inline double dis(node a,node b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline int in_circle(node a){return dis(a,res)<=r?1:0;}
inline void get_circle(node p1,node p2,node p3){
	double a=p1.x-p2.x,b=p1.y-p2.y,c=p1.x-p3.x,d=p1.y-p3.y;
	double e=((p1.x*p1.x-p2.x*p2.x)-(p2.y*p2.y-p1.y*p1.y))/2;
	double f=((p1.x*p1.x-p3.x*p3.x)-(p3.y*p3.y-p1.y*p1.y))/2;
	res.x=(b*f-d*e)/(b*c-a*d),res.y=(c*e-a*f)/(b*c-a*d);
	r=dis(res,p1);
}
void solve(){
	random_shuffle(t+1,t+1+n);
	for(int i=1;i<=n;i++){
		if(!in_circle(t[i])){
			res=t[i],r=0;
			for(int j=1;j<i;j++){
				if(!in_circle(t[j])){
					res.x=(t[i].x+t[j].x)/2,res.y=(t[i].y+t[j].y)/2;
					r=dis(t[i],res);
					for(int k=1;k<j;k++){
						if(!in_circle(t[k])){
							get_circle(t[i],t[j],t[k]);
						}
					}
				}
			}
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	scanf("%lf %lf",&t[i].x,&t[i].y);
	solve();
	printf("%.10lf\n",r);
	printf("%.10lf %.10lf\n",res.x,res.y);
	return 0;
}