题解 P2533 【[AHOI2012]信号塔】
消失的海岸线
2017-09-19 15:54:06
人话题意：给出平面上 N 个点,N<=10^6，请求出一个半径最小的圆覆盖住所有的点，并求出该点的坐标与半径。
即经典的最小圆覆盖问题，在此我们介绍随机增量法：
随机增量法是一个可以在 **期望**$O(n)$ 时间内求出最小圆覆盖的算法，首先它的算法流程是这样的
枚举第一个点 $i$，若不在目前圆内，设它为圆心
枚举第二个点 $j$，若不在当前圆内，设当前圆为以 $i,j$ 为直径的圆
枚举第三个点 $k$，若不在当前圆内，设当前圆为 $i,j,k$ 的外接圆
###正确性
显然最优解一定是两个点为直径的圆或者一个三角形的外接圆，否则肯定能缩的更小。那么这么枚举的正确性是比较显然的了
###时间复杂度
这是一个重点，这么做看似是$O(n^3)$ 的，不过对于**随机顺序**的点，是可以**期望**$ O(n)$ 的。下面考虑证明：
显然，最后一层循环枚举从 $1~j$，只要进入循环就一定要跑完，所以是$O(j)$ 的
考虑倒数第二层循环，什么情况下会进入第三层循环呢？仅当 $j$ 不在前 $j-1$ 个点形成的圆中，考虑 $j$ 个点形成的圆是由三个点确定的，那么第 $j$ 个 (最后一个点) 若是三个点之一，则需要扩大圆，否则不需要进入第三层循环，这个概率是$\frac{3}{j}$ 的，所以第二层的复杂度是$O(i)$ 的
同理，第一层的复杂度就是$O(n)$ 的了
###实现
以此题为例，给出在下的AC代码：
```cpp
#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 500010
#define eps 1e-6
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct point
{
double x,y;
}a[N],O;
double R;
int n;
double dis(point x,point y)
{return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
bool in_cir(point x)
{return dis(x,O)-R<eps;}
point get_O(point x1,point x2,point x3)
{
double a,b,c,d,e,f;
point ans;
a=x2.x-x1.x,b=x2.y-x1.y,c=x3.x-x2.x,d=x3.y-x2.y;
e=x2.x*x2.x+x2.y*x2.y-x1.x*x1.x-x1.y*x1.y;
f=x3.x*x3.x+x3.y*x3.y-x2.x*x2.x-x2.y*x2.y;
ans.x=(f*b-e*d)/(c*b-a*d)/2;
ans.y=(a*f-e*c)/(a*d-b*c)/2;
return ans;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
scanf("%lf %lf",&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)
swap(a[i],a[rand()%n+1]);
O=a[1];
for(int i=1;i<=n;i++)
if(!in_cir(a[i]))
{
O=a[i];
for(int j=1;j<i;j++)
if(!in_cir(a[j]))
{
O.x=(a[i].x+a[j].x)/2;
O.y=(a[i].y+a[j].y)/2;
R=dis(a[i],a[j])/2;
for(int k=1;k<j;k++)
if(!in_cir(a[k]))
{
O=get_O(a[i],a[j],a[k]);
R=dis(O,a[i]);
}
}
}
printf("%.2lf %.2lf %.2lf",O.x,O.y,R);
}
```
为了避免可能存在的markdown格式错误，可以在本人的博客中看到同样的内容
http://www.zgz233.xyz/2017/07/10/bzoj-133613372823-balkan2002alien%E6%9C%80%E5%B0%8F%E5%9C%86%E8%A6%86%E7%9B%96ahoi2012%E4%BF%A1%E5%8F%B7%E5%A1%94/