1337传送门
1336传送门
随机增量法求最小圆覆盖。
假如已经求出了前i-1个点的最小圆覆盖，假如第i个点后，如果不在所求的圆內，那么这个点一定在新圆的边界上。这样我们只要枚举另外两个点就可以了，因为三点确定一个圆。
枚举方法为：从1-(i-1)枚举一个不在圆內的点j，再从1-(j-1)枚举一个不在圆內的点k，那么i j k三点就可以确定一个圆。(注意三点共线的特殊情况)
这样的枚举方法一定可以保证枚举到所有的点对，从而保证所有点在圆內且圆最小。
但是这tm是O（N^3）的。
可是tm就驶过去了。（一脸懵逼.jpeg）
及时他来卡你，大力random_shuffle已发也可以呀。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
double r,q[4][4];
struct P{double x,y;}o,p[100005];
double dis(P a,P b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void change(P a,P b,P c){
q[1][1]=2*(b.x-a.x); q[1][2]=2*(b.y-a.y);
q[1][3]=(b.x*b.x+b.y*b.y-a.x*a.x-a.y*a.y);
q[2][1]=2*(c.x-a.x); q[2][2]=2*(c.y-a.y);
q[2][3]=(c.x*c.x+c.y*c.y-a.x*a.x-a.y*a.y);
for (int i=1;i<=2;i++)
for (int j=1;j<=2;j++)
if (i!=j){
double x=q[j][i]/q[i][i];
for (int k=1;k<=3;k++)
q[j][k]-=x*q[i][k];
}
o.x=q[1][3]/q[1][1];
o.y=q[2][3]/q[2][2];
r=dis(o,a);
}
int main(){
srand(20170511);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
random_shuffle(p+1,p+n+1);
o=p[1];
for (int i=2;i<=n;i++)
if (dis(o,p[i])>r){
o.x=(p[1].x+p[i].x)/2;
o.y=(p[1].y+p[i].y)/2;
r=dis(o,p[i]);
for (int j=2;j<i;j++)
if (dis(o,p[j])>r){
o.x=(p[j].x+p[i].x)/2;
o.y=(p[j].y+p[i].y)/2;
r=dis(o,p[i]);
for (int k=1;k<j;k++)
if (dis(o,p[k])>r)
change(p[i],p[j],p[k]);
}
}
printf("%.3lf",sqrt(r));
}