题意
给\(n\)个点，求一个能覆盖所有点的面积最小的圆。（\(n \le 50000\)）
分析
随机增量法
题解
理论上\(O(n^3)\)暴力，实际上加上随机化后期望是\(O(n)\)的。
算法大概就是：
假设我们已经得到了最小覆盖圆\(O\)，然后现在考虑假如第\(i\)个点进去。
如果第\(i\)个点在圆内或在圆上，则不需要更改。如果在圆外，显然最小覆盖圆要经过这个点。
于是又从头考虑\(1 \sim i-1\)这些点，我们只需要找到一个经过\(i\)点的覆盖所有点的最小覆盖圆。于是同前面一步一直类推下去。
直到出现了最小覆盖圆要经过三个点。于是三点确定一个圆就行了。
#include <bits/stdc++.h>
using namespace std;
typedef double lf;
const int N=1000005;
const lf eps=1e-8;
int n;
struct ip {
lf x, y;
ip(lf _x=0, lf _y=0) : x(_x), y(_y) { }
void scan() {
scanf("%lf%lf", &x, &y);
}
}a[N];
inline lf sqr(lf a) {
return a*a;
}
inline lf dist(ip &a, ip &b) {
return sqr(a.x-b.x)+sqr(a.y-b.y);
}
inline ip getO(ip &a, ip &b, ip &c) {
lf x1=b.x-a.x, y1=b.y-a.y, z1=(sqr(x1)+sqr(y1))/2,
x2=c.x-a.x, y2=c.y-a.y, z2=(sqr(x2)+sqr(y2))/2,
s=x1*y2-x2*y1;
if(s>-eps && s<eps) {
if(x1*x2<-eps) {
return ip((b.x+c.x)/2, (b.y+c.y)/2);
}
return ip((a.x+c.x)/2, (a.y+c.y)/2);
}
return ip(a.x+(z1*y2-z2*y1)/s, a.y+(x1*z2-x2*z1)/s);
}
inline int rand() {
typedef long long ll;
static ll mo=1e9+7, g=78125, now=2333;
return (now*=g)%=mo;
}
int main() {
scanf("%d", &n);
for(int i=0; i<n; ++i) {
a[i].scan();
if(i) {
swap(a[i], a[rand()%i]);
}
}
ip o=a[0];
lf r=0;
for(int i=1; i<n; ++i) {
if(dist(a[i], o)-r>eps) {
o=a[i];
r=0;
for(int j=0; j<i; ++j) {
if(dist(a[j], o)-r>eps) {
o=ip((a[i].x+a[j].x)/2, (a[i].y+a[j].y)/2);
r=dist(a[i], o);
for(int k=0; k<j; ++k) {
if(dist(a[k], o)-r>eps) {
o=getO(a[i], a[j], a[k]);
r=dist(a[k], o);
}
}
}
}
}
}
printf("%.2f %.2f %.2f\n", o.x, o.y, sqrt(r));
return 0;
}