自动搬运

查看原文

来自洛谷，原作者为

	消失的海岸线 **

搬运于2025-08-24 21:38:45，当前版本为作者最后更新于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代码：

#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最小圆覆盖ahoi2012信号塔/