最小圆覆盖（板子）

当点的顺序被打乱：
时间复杂度：$O(N)$
空间复杂度：$O(N)$
否则，时间复杂度可能为$O(N^3)$

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
const double eps=1e-12;
double R;
int n;
struct node
{
   
	double x,y;
}point[N],O;

double getDistance(node p)//与圆心之间的距离
{
   
	return sqrt((p.x-O.x)*(p.x-O.x)+(p.y-O.y)*(p.y-O.y));
}
void getCircle(node p1,node p2,node p3)//三点确定圆心
{
   
    double a,b,c,d,e,f;
    a=p1.x-p2.x;
    b=p1.y-p2.y;
    c=p1.x-p3.x;
    d=p1.y-p3.y;
    e=p1.x*p1.x+p1.y*p1.y-p2.x*p2.x-p2.y*p2.y;
    f=p1.x*p1.x+p1.y*p1.y-p3.x*p3.x-p3.y*p3.y;
    O.x=(b*f-d*e)/(2*b*c-2*a*d);
    O.y=(c*e-a*f)/(2*b*c-2*a*d);
    R=getDistance(p1);
}
bool inCircle(node p)//判断是否在园内
{
   
    return R>=getDistance(p)+eps;
}
void minCircle()//最小圆
{
   
    O=point[0];
    R=0;
    for(int i=0;i<n;i++)
    {
   
        if(!inCircle(point[i]))
        {
   
            O=point[i];
            R=0;
            for(int j=0;j<i;j++)
            {
   
                if(!inCircle(point[j]))
                {
   
                    O.x=(point[i].x+point[j].x)/2;
                    O.y=(point[i].y+point[j].y)/2;
                    R=getDistance(point[j]);
                    for(int k=0;k<j;k++)
                    {
   
                        if(!inCircle(point[k]))
                        {
   
                            getCircle(point[i],point[j],point[k]);
                        }
                    }
                }
            }
        }
    }
}
int main()
{
   
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%lf%lf",&point[i].x,&point[i].y);
    random_shuffle(point,point+n);//将点的次序打乱，使算法复杂度趋向于O（N）
    minCircle();
    printf("%.10f",R);
}