题目
给出 N 个点，让你画一个最小的包含所有点的圆。
分析
使用随机增量法，提前将点打乱保证期望是 \(O(n)\) 的
每次对于第 \(i\) 个点，如果它在前 \(i-1\) 个点的最小外接圆内，那么这个圆就是前 \(i\) 个点的最小外接圆。
否则第 \(i\) 个点就在前 \(i\) 个点的最小外接圆上，需要在前 \(i-1\) 个点上找到其它两点。
不妨暂时让圆心定在第 \(i\) 个点，不断重新寻找新的外接圆圆心，在固定第一个点时如果第一个点在圆外说明它也在圆上。
固定了两个点后圆心就是中点，固定第二个点时如果第二个点在圆外说明它也在圆上，确定三点后联立方程求外接圆。
复杂度貌似就是打乱之后每个点被选中当外接圆上的点的概率是 \(\frac{3}{n}\)，然后就是 \(O(n)\) 的了。
代码
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
const long double eps=1e-11;
struct Point{
long double x,y;
Point operator -(const Point &t)const{
return (Point){x-t.x,y-t.y};
}
}a[100011],ans;
int n; long double ansr;
long double o(Point t){return sqrt(t.x*t.x+t.y*t.y);}
void Circumcircle(Point x,Point y,Point z){
long double a1=2*(y.x-x.x),b1=2*(y.y-x.y),c1=y.x*y.x-x.x*x.x+y.y*y.y-x.y*x.y;
long double a2=2*(z.x-x.x),b2=2*(z.y-x.y),c2=z.x*z.x-x.x*x.x+z.y*z.y-x.y*x.y;
ans.y=(c1*a2-c2*a1)/(b1*a2-b2*a1),ans.x=(c1-b1*ans.y)/a1,ansr=o(ans-x);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for (int i=1;i<=n;++i) cin>>a[i].x>>a[i].y;
random_shuffle(a+1,a+1+n);
random_shuffle(a+1,a+1+n);
ans=a[1],ansr=0;
for (int i=2;i<=n;++i)
if (o(a[i]-ans)>ansr+eps){
ans=a[i],ansr=0;
for (int j=1;j<i;++j)
if (o(a[j]-ans)>ansr+eps){
ans=(Point){(a[i].x+a[j].x)/2,(a[i].y+a[j].y)/2},ansr=o(ans-a[j]);
for (int k=1;k<j;++k) if (o(a[k]-ans)>ansr+eps) Circumcircle(a[i],a[j],a[k]);
}
}
cout<<fixed<<setprecision(11)<<ansr<<'\n'<<ans.x<<' '<<ans.y;
return 0;
}