BZOJ1336 Balkan2002 Alien最小圆覆盖

Description

给出N个点，让你画一个最小的包含所有点的圆。

Input

先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)

Output

输出圆的半径，及圆心的坐标

Sample Input

6
8.0 9.0
4.0 7.5
1.0 2.0
5.1 8.7
9.0 2.0
4.5 1.0

Sample Output

5.00
5.00 5.00

最小圆覆盖模板，随机增量法，只需要YY一下怎么利用三点确定圆心就好了

一开始写模拟退火无奈GG，后面也是看看正解才知道有这么一个玩意，很神奇，不过挺巧妙的

其实说实话呢，不加随机打乱节点顺序也可以过，大概是个假随机吧，其实就是O(n3)O(n3)枚举

照着黄学长代码打的。。涨姿势了

#include<bits/stdc++.h>

using namespace std;

#define eps 1e-12

#define N 100010

struct Node{double x,y;}p[N],ans;

int n;

double R;

double dis(Node a,Node b){

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

bool cmp(double a,double b){

    return fabs(a-b)<eps;

}

Node geto(Node a,Node b,Node c){

    double a1=2*(b.x-a.x);

    double a2=2*(c.x-a.x);

    double b1=2*(b.y-a.y);

    double b2=2*(c.y-a.y);

    double c1=b.x*b.x-a.x*a.x+b.y*b.y-a.y*a.y;

    double c2=c.x*c.x-a.x*a.x+c.y*c.y-a.y*a.y;

    Node o;

    if(cmp(a1,0)){

        o.y=c1/b1;

        o.x=(c2-ans.y*b2)/a2;

    }else if(cmp(b1,0)){

        o.x=c1/a1;

        o.y=(c2-ans.x*a2)/b2;

    }else{

        o.x=(c2*b1-c1*b2)/(a2*b1-a1*b2);

        o.y=(c2*a1-c1*a2)/(b2*a1-b1*a2);

    }

    return o;

}

int main(){

    scanf("%d",&n);

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

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

        swap(p[rand()%n+1],p[rand()%n+1]);

    ans=p[1];

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

        double tmp1=dis(ans,p[i]);

        if(tmp1<R||cmp(tmp1,R))continue;

        ans.x=(p[i].x+p[1].x)/2;

        ans.y=(p[i].y+p[1].y)/2;

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

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

            tmp1=dis(ans,p[j]);

            if(tmp1<R||cmp(tmp1,R))continue;

            ans.x=(p[i].x+p[j].x)/2;

            ans.y=(p[i].y+p[j].y)/2;

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

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

                tmp1=dis(ans,p[k]);

                if(tmp1<R||cmp(tmp1,R))continue;

                ans=geto(p[i],p[j],p[k]);

                R=dis(ans,p[i]);

            }

        }

    }

    printf("%.10lf\n%.10lf %.10lf",R,ans.x,ans.y);

    return 0;

}

巴特西

BZOJ1336 Balkan2002 Alien最小圆覆盖【随机增量法】*

BZOJ1336 Balkan2002 Alien最小圆覆盖

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

BZOJ1336 Balkan2002 Alien最小圆覆盖 【随机增量法】*

BZOJ1336 Balkan2002 Alien最小圆覆盖

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

BZOJ1336 Balkan2002 Alien最小圆覆盖【随机增量法】*