P2533 [AHOI2012]信号塔

据说是一个叫做随机增量法的东西

枚举\(i\)，如果不在圆中将它设为圆心

枚举\(j\)，如果不在圆中将\((i,j)\)成为新的圆的直径

枚举\(k\)，如果不在圆中让\(i,j,k\)组成的三角形的外接圆成为新的圆

据说在随机数据的情况下期望\(O(n)\)，所以要在读进来的时候random_shuffle一下

主要是求三角形外接圆的圆心太恶心了……大概是这样的（图是偷来的）

//minamoto

#include<bits/stdc++.h>

#define rint register int

#define eps 1e-6

using namespace std;

const int N=5e5+5;

struct node{double x,y;}p[N],C;

int n;double R;

inline double dis(const node &a,const node &b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

inline bool in(const node &x){return dis(x,C)-R<eps;}

node get(node A,node B,node C){

    node res;

    double a1=B.x-A.x,a2=C.x-A.x;

    double b1=B.y-A.y,b2=C.y-A.y;

    double c1=(a1*a1+b1*b1)/2.0;

    double c2=(a2*a2+b2*b2)/2.0;

    double d=a1*b2-a2*b1;

    res.x=A.x+(c1*b2-c2*b1)/d;

    res.y=A.y+(c2*a1-c1*a2)/d;return res;

}

void solve(){

    random_shuffle(p+1,p+1+n),C=p[1],R=0;

    for(rint i=1;i<=n;++i)if(!in(p[i])){

        C=p[i],R=0;for(rint j=1;j<i;++j)if(!in(p[j])){

            C.x=(p[i].x+p[j].x)/2,C.y=(p[i].y+p[j].y)/2;

            R=dis(p[i],p[j])/2;

            for(rint k=1;k<j;++k)if(!in(p[k]))

            C=get(p[i],p[j],p[k]),R=dis(C,p[i]);

        }

    }

}

int main(){

//	freopen("testdata.in","r",stdin);

    srand(20030719);

    scanf("%d",&n);

    for(rint i=1;i<=n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);

    solve();

    printf("%.2lf %.2lf %.2lf\n",C.x,C.y,R);return 0;

}

巴特西

P2533 [AHOI2012]信号塔

最新文章

热门文章