AHOI2012 信号塔 | 最小圆覆盖模板

题目链接：戳我

最小圆覆盖。

1、枚举第一个点，考虑当前圆是否包含了这个点，如果没有，则把圆变成以这个点为圆心，半径为0的圆。

2、枚举第二个点，考虑圆是否包含了这个点，如果没有，则把圆变成以这两个点的中点为圆心，半径为两点距离一半的圆。

3、枚举第三个点，节点是否在圆内，如果不在，直接把圆变成这三个点的外接圆。具体怎么做，就是解方程（文化课应该在九年级数学讲到过）

记得要打乱点的顺序！期望时间复杂度为\(O(n)\)（具体为什么我也不知道，但是或许可以感性地理解一下。。。）

另外，如果不想掉精度太严重，还是建议除法都移项，换成乘法。

update:2019.4.4

代码如下：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<ctime>

#define eps 1e-15

#define MAXN 500010

using namespace std;

int n;

double r;

struct Node{double x,y;}node[MAXN],o;

inline double dist(Node a,Node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

inline void solve(Node A,Node B,Node C)

{

    double a=(B.x-C.x)*2;

    double b=(B.y-C.y)*2;

    double c=(A.x-B.x)*2;

    double d=(A.y-B.y)*2;

    double e=(B.x*B.x-C.x*C.x)+(B.y*B.y-C.y*C.y);

    double f=(A.x*A.x-B.x*B.x)+(A.y*A.y-B.y*B.y);

    o.x=(d*e-b*f)/(a*d-b*c);

    o.y=(c*e-a*f)/(b*c-a*d);

    r=dist(A,o);

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("ce.in","r",stdin);

    #endif

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%lf%lf",&node[i].x,&node[i].y);

    random_shuffle(&node[1],&node[n+1]);

    o.x=node[1].x,o.y=node[1].y;r=0;

    for(int i=2;i<=n;i++)

    {

        if(dist(node[i],o)>r+eps)

        {

            o=node[i];r=0;

            for(int j=1;j<i;j++)

            {

                if(dist(node[j],o)>r+eps)

                {

                    o.x=(node[j].x+node[i].x)/2;

                    o.y=(node[j].y+node[i].y)/2;

                    r=dist(o,node[i]);

                    for(int k=1;k<j;k++)

                    {

                        if(dist(node[k],o)>eps+r)

                            solve(node[k],node[i],node[j]);

                    }

                }

            }

        }

    }

    printf("%.2lf %.2lf %.2lf\n",o.x,o.y,r);

    return 0;

}