看了下最小圆覆盖的随机增量算法……orz

大概的框架是这样:

随机打乱所有点
初始化圆为1,2两个点为直径的圆
for i in (3,n+1) :
if i不在当前圆内 :
设圆为1,i两个点为直径的圆
for j in (1,i) :
if j不在当前圆内 :
设圆为j,i两个点为直径的圆
for k in (1,j) :
if k不在当前圆内 :
设圆为i,j,k三个点确定的圆

在随机打乱的前提下,可以使用期望证明整个算法的复杂度是O(n)的。

代码:

random_shuffle(a+1,a+n+1);
cx=(a[1].x+a[2].x)*0.5;
cy=(a[1].y+a[2].y)*0.5;
r=dist(a[1].x,a[1].y,a[2].x,a[2].y)*0.5;
for(int i=3;i<=n;i++)
if(dist(a[i].x,a[i].y,cx,cy)>r)
{
    cx=(a[1].x+a[i].x)*0.5;
    cy=(a[1].y+a[i].y)*0.5;
    r=dist(a[1].x,a[1].y,a[i].x,a[i].y)*0.5;
    for(int j=2;j<i;j++)
    if(dist(a[j].x,a[j].y,cx,cy)>r)
    {
        cx=(a[j].x+a[i].x)*0.5;
        cy=(a[j].y+a[i].y)*0.5;
        r=dist(a[j].x,a[j].y,a[i].x,a[i].y)*0.5;
        for(int k=1;k<j;k++)
        if(dist(a[k].x,a[k].y,cx,cy)>r)
        {
            double p1=2*(a[i].x-a[j].x),
                    p2=2*(a[i].y-a[j].y),
                    p3=2*(a[i].x-a[k].x),
                    p4=2*(a[i].y-a[k].y),
                    q1=a[i].x*a[i].x+a[i].y*a[i].y-a[j].x*a[j].x-a[j].y*a[j].y,
                    q2=a[i].x*a[i].x+a[i].y*a[i].y-a[k].x*a[k].x-a[k].y*a[k].y;
            cy=(q2*p1/p3-q1)/(p4*p1/p3-p2);
            cx=(q1-p2*cy)/p1;
            r=dist(a[i].x,a[i].y,cx,cy);
        }
    }
}

Comments

comments powered by Disqus