ACM计算几何最小圆覆盖算法

个人收集整理资料， 仅供交流学习， 勿作商业用途

1 / 8 平面上有n个点，给定n个点的坐标，试找一个半径最小的圆，将n 个点全部包围，点可以在圆上。

1. 在点集中任取3点A,B,C。

2. 作一个包含A,B,C三点的最小圆,圆周可能通过这3点，也可能只通过其中两点,但包含第3点.后一种情况圆周上的两点一定是位于圆的一条直径的两端。

3. 在点集中找出距离第2步所建圆圆心最远的D点，若D点已在圆内或圆周上，则该圆即为所求的圆，算法结束.则，执行第4步。

4. 在A,B,C,D中选3个点,使由它们生成的一个包含这4个点的圆为最小，这3 点成为新的A,B,C，返回执行第2步。若在第4步生成的圆的圆周只通过A,B,C,D 中的两点，则圆周上的两点取成新的A和B,从另两点中任取一点作为新的C。

程序设计题解上的解题报告：

对于一个给定的点集A，记MinCircle(A)为点集A的最小外接圆，显然，对于所有的点集情况A,MinCircle(A)都是存在且惟一的。需要特别说明的是，当A为空集时，MinCircle(A)为空集，当A={a}时，MinCircle(A)圆心坐标为a，半径为0；显然，MinCircle(A)可以有A边界上最多三个点确定(当点集A中点的个数大于 1时，有可能两个点确定了MinCircle(A))，也就是说存在着一个点集B，|B|<=3

且B包含与A，有MinCircle(B)=MinCircle(A).所以，如果a不属于B，则 MinCircle(A-{a})=MinCircle(A)。如果MinCircle(A-{a})不等于个人收集整理资料， 仅供交流学习， 勿作商业用途

2 / 8 MinCircle(A),则 a属于B。所以我们可以从一个空集R开始，不断的把题目中给定的点集中的点加入R，同时维护R的外接圆最小，这样就可以得到解决该题的算法。

不断添加圆，维护最小圆。如果添加的点i在圆内，不动，否则：

问题转化为求1~I的最小圆：求出1与I的最小圆，并且扫描j=2~I-1，维护（1）+（i）+(2~j)的最小圆，如果找到J不在最小圆内，问题转化为：求(1~J)+(i)的最小圆。求出I与J的最小圆，继续扫描K=1~j-1,找到第一个不在最小圆内的，求出I J K三者交点即可，此时找到了(1~j)+(i)的最小圆，可以回到上一步（三点定一圆，所以1~J-1一定都在求出的最小圆上）。

实际上利用了这么个定理：

若I不在1~I-1的最小圆上，则I在1~I的最小圆上。

若J不在(i)+(1~j-1)的最小圆上，则j在(i)+(1~J)的最小圆上。

证明可以考虑这么做：最小圆必定是可以通过不断放大半径，直到所有以任意点为圆心，半径为半径的圆存在交点，此时的半径就是最小圆。所以上述定理可以通过这个思想得到。

这个做法复杂度是O(n)的，当加入圆的顺序随机时，因为三点定一圆，所以不在圆内概率是3/i,求出期望可得是On.

个人收集整理资料， 仅供交流学习， 勿作商业用途

3 / 8

6.最小包围圆：

坐标系上有多点画一个最小圆包含所有点求出这个圆的圆心坐标和半径

本人解题思路：

设想一个足够大的圆逐渐缩小这个圆并移动这个圆直到有两点在这个圆周上如果这两点的连线不是这个圆的直径

那就说明还可以移动缩小这个圆直到出现另一个点在这个圆周上这个三个点所确定的圆就是所要求的圆。

实现思路：

先求出两点间的最长距离。以这两点的距离为直径画一个圆，如果包含了所有的点那么就是所求的解。如果不能包含就说明有三点及三点在这个圆上根据三点确定一个圆只要枚举出所有的三点成立的圆再比较所有成立的圆的半径最小的就是所求的点。 个人收集整理资料， 仅供交流学习， 勿作商业用途

4 / 8

#include

#include

struct TPoint

{

double x,y。

}。

TPoint a[1005],d。

double r。

double distance(TPoint p1, TPoint p2)

{

return (sqrt((p1.x-p2.x)*(p1.x -p2.x)+(p1.y-p2.y)*(p1.y-p2.y)))。

}

double multiply(TPoint p1, TPoint p2, TPoint p0)

{

return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y))。

}

void MiniDiscWith2Point(TPoint p,TPoint q,int n)

{

d.x=(p.x+q.x)/2.0。

d.y=(p.y+q.y)/2.0。 个人收集整理资料， 仅供交流学习， 勿作商业用途

5 / 8 r=distance(p,q)/2。

int k。

double c1,c2,t1,t2,t3。

for(k=1。k<=n。k++)

{

if(distance(d,a[k])<=r)continue。

if(multiply(p,q,a[k])!=0.0)

{

c1=(p.x*p.x+p.y*p.y-q.x*q.x-q.y*q.y)/2.0。

c2=(p.x*p.x+p.y*p.y-a[k].x*a[k].x-a[k].y*a[k].y)/2.0。

d.x=(c1*(p.y-a[k].y)-c2*(p.y-q.y))/((p.x-q.x)*(p.y-a[k].y)-(p.x-a[k].x)*(p.y-q.y))。

d.y=(c1*(p.x-a[k].x)-c2*(p.x-q.x))/((p.y-q.y)*(p.x-a[k].x)-(p.y-a[k].y)*(p.x-q.x))。

r=distance(d,a[k])。

}

else

{

t1=distance(p,q)。

t2=distance(q,a[k])。

t3=distance(p,a[k])。 个人收集整理资料， 仅供交流学习， 勿作商业用途

6 / 8 if(t1>=t2&&t1>=t3)

{d.x=(p.x+q.x)/2.0。d.y=(p.y+q.y)/2.0。r=distance(p,q)/2.0。}

else if(t2>=t1&&t2>=t3)

{d.x=(a[k].x+q.x)/2.0。d.y=(a[k].y+q.y)/2.0。r=distance(a[k],q)/2.0。}

else

{d.x=(a[k].x+p.x)/2.0。d.y=(a[k].y+p.y)/2.0。r=distance(a[k],p)/2.0。}

}

}

}

void MiniDiscWithPoint(TPoint pi,int n)

{

d.x=(pi.x+a[1].x)/2.0。

d.y=(pi.y+a[1].y)/2.0。

r=distance(pi,a[1])/2.0。

int j。

for(j=2。j<=n。j++)

{

if(distance(d,a[j])<=r)continue。

else

{

MiniDiscWith2Point(pi,a[j],j-1)。 个人收集整理资料， 仅供交流学习， 勿作商业用途

7 / 8 }

}

}

int main()

{

int i,n。

while(scanf("%d",&n)&&n)

{

for(i=1。i<=n。i++)

{

scanf("%lf %lf",&a[i].x,&a[i].y)。

}

if(n==1)

{ printf("%.2lf %.2lf 0.00\n",a[1].x,a[1].y)。continue。}

r=distance(a[1],a[2])/2.0。

d.x=(a[1].x+a[2].x)/2.0。

d.y=(a[1].y+a[2].y)/2.0。

for(i=3。i<=n。i++)

{

if(distance(d,a[i])<=r)continue。 个人收集整理资料， 仅供交流学习， 勿作商业用途

8 / 8 else

MiniDiscWithPoint(a[i],i-1)。

}

printf("%.2lf %.2lf %.2lf\n",d.x,d.y,r)。

}

return 0。

}