bzoj2823: [AHOI2012]信号塔&&1336: [Balkan2002]Alien最小圆覆盖&&1337: 最小圆覆盖

首先我写了个凸包就溜了

这是最小圆覆盖问题，今晚学了一下

先随机化点，一个个加入

假设当前圆心为o，半径为r，加入的点为i

若i不在圆里面，令圆心为i，半径为0

再重新从1~i-1不停找j不在圆里面，令圆心为ij中点，直径为ij距离

再重新在1~j-1不停找k不在圆里面，三点可确定一圆，初中数学

复杂度看似O(n^3)实则O(n)，好玄学

坑点：注意如果用点斜式表示方程有斜率为不存在的情况，需要特判

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const double eps=1e-;

double sqr(double x){return x*x;}

struct point{ double x,y;point(){} point(double X,double Y){x=X,y=Y;} };

double getdis(point p1,point p2){return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));}

point  middle(point p1,point p2){return point((p1.x+p2.x)/,(p1.y+p2.y)/);}

double slope (point p1,point p2)

{

    if(p2.x==p1.x)return ;

    return (p2.y-p1.y)/(p2.x-p1.x);

}

double multi(point p1,point p2,point p0)

{

    double x1,y1,x2,y2;

    x1=p1.x-p0.x;

    y1=p1.y-p0.y;

    x2=p2.x-p0.x;

    y2=p2.y-p0.y;

    return x1*y2-x2*y1;

}

struct segment{ double k,b;segment(){} segment(double K,double B){k=K,b=B;} };

segment getseg(double k,point pp){return segment(k,pp.y-k*pp.x);}

point intersection(segment s1,segment s2)

{

    double x=(s2.b-s1.b)/(s1.k-s2.k);

    double y=s1.k*x+s1.b;

    return point(x,y);

}

//--------------------------------------simple--------------------------------------------------------

int n; point p[];

bool cmp(point p1,point p2)

{

    double d=multi(p1,p2,p[]);

    if(fabs(d)<=eps)return getdis(p1,p[])<getdis(p2,p[]);

    else return d>;

}

int top,sta[];

void graham()

{

    sort(p+,p+n+,cmp);

    top=;sta[++top]=,sta[++top]=;

    double g;

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

    {

        while(top>=)

        {

            g=multi(p[sta[top]],p[i],p[sta[top-]]);

            if(g<||fabs(g)<=eps)top--;

            else break;

        }

        sta[++top]=i;

    }

}

//------------------------------------graham----------------------------------------------------------

point getcore(point p1,point p2,point p3)

{

    double g=multi(p1,p2,p3);

    if(fabs(g)<=eps)

    {

        double d1=getdis(p1,p2),d2=getdis(p1,p3),d3=getdis(p2,p3);

        if(d1>d2&&d1>d3)return middle(p1,p2);

        if(d2>d1&&d2>d3)return middle(p1,p3);

        if(d3>d1&&d3>d2)return middle(p2,p3);

    }

    else

    {

        segment s1,s2;

        if(slope(p1,p2)==)

        {

            s1=getseg(-/slope(p1,p3),middle(p1,p3));

            s2=getseg(-/slope(p2,p3),middle(p2,p3));

        }

        else if(slope(p1,p3)==)

        {

            s1=getseg(-/slope(p1,p2),middle(p1,p2));

            s2=getseg(-/slope(p2,p3),middle(p2,p3));

        }

        else

        {

            s1=getseg(-/slope(p1,p2),middle(p1,p2));

            s2=getseg(-/slope(p1,p3),middle(p1,p3));

        }

        return intersection(s1,s2);

    }

}

void circlecover()

{

    random_shuffle(sta+,sta+top+);

    point o=p[sta[]];double r=,d;

    for(int i=;i<=top;i++)

        if(getdis(o,p[sta[i]])>r)

        {

            o=p[sta[i]],r=;

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

                if(getdis(o,p[sta[j]])>r)

                {

                    o=middle(p[sta[i]],p[sta[j]]),r=getdis(o,p[sta[i]]);

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

                        if(getdis(o,p[sta[k]])>r)

                            o=getcore(p[sta[i]],p[sta[j]],p[sta[k]]),r=getdis(o,p[sta[i]]);

                }

        }

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

}

//------------------------------------solve----------------------------------------------------------

int main()

{

    scanf("%d",&n);

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

    {

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

        if(p[i].y<p[].y||(p[i].y==p[].y&&p[i].x<p[].x))

            swap(p[i],p[]);

    }

    graham();

    circlecover();

    return ;

}