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

1、平面上有 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 步生成

2、的圆的圆周只通过 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) ，也就是说存在着一

3、个点集 B，|B|<=3且 B 包含与 A，有 MinCircle(B)=MinCircle(A). 所以，如果 a 不属于B，则 MinCircle(A-a)=MinCircle(A)。如果 MinCircle(A-a) 不等于1 / 8MinCircle(A), 则 a 属于 B。所以我们可以从一个空集R 开始，不断的把题目中给定的点集中的点加入R，同时维护R 的外接圆最小，这样就可以得到解决该题的算法。不断添加圆，维护最小圆。如果添加的点i 在圆内，不动，否则：问题转化为求 1I 的最小圆：求出 1 与 I 的最小圆，并且扫描 j=2I-1 ，维护（ 1）+（i ）+(2j) 的最

4、小圆，如果找到 J 不在最小圆内，问题转化为：求 (1J)+(i) 的最小圆。求出 I 与 J 的最小圆，继续扫描 K=1j-1, 找到第一个不在最小圆内的，求出I J K三者交点即可，此时找到了(1j)+(i)的最小圆，可以回到上一步（三点定一圆，所以1J-1 一定都在求出的最小圆上）。实际上利用了这么个定理：若 I 不在 1I-1 的最小圆上，则I 在 1I 的最小圆上。若 J 不在 (i)+(1j-1)的最小圆上，则j 在 (i)+(1J)的最小圆上。证明可以考虑这么做：最小圆必定是可以通过不断放大半径，直到所有以任意点为圆心，半径为半径的圆存在交点，此时的半径就是最小圆。所以上述定理可

5、以通过这个思想得到。这个做法复杂度是 O(n) 的，当加入圆的顺序随机时，因为三点定一圆，所以不在圆内概率是 3/i, 求出期望可得是 On.2 / 86.最小包围圆：坐标系上有多点画一个最小圆包含所有点求出这个圆的圆心坐标和半径本人解题思路：设想一个足够大的圆逐渐缩小这个圆并移动这个圆直到有两点在这个圆周上如果这两点的连线不是这个圆的直径那就说明还可以移动缩小这个圆直到出现另一个点在这个圆周上这个三个点所确定的圆就是所要求的圆。实现思路：先求出两点间的最长距离。以这两点的距离为直径画一个圆，如果包含了所有的点那么就是所求的解。如果不能包含就说明有三点及三点在这个圆上根据三点确定一个圆只要枚举

6、出所有的三点成立的圆再比较所有成立的圆的半径最小的就是所求的点。3 / 8#include<stdio.h>#include<math.h>structTPointdouble x,y。TPoint a1005,d。double r。doubledistance(TPointp1,TPointp2)return (sqrt(p1.x-p2.x)*(p1.x -p2.x)+(p1.y-p2.y)*(p1.y-p2.y)。double multiply(TPointp1,TPointp2,TPointp0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.

7、x-p0.x)*(p1.y-p0.y)。void MiniDiscWith2Point(TPointp,TPointq,intn)d.x=(p.x+q.x)/2.0。d.y=(p.y+q.y)/2.0。4 / 8r=distance(p,q)/2。int k。double c1,c2,t1,t2,t3。for(k=1。k<=n。k+)if(distance(d,ak)<=r)continue。if(multiply(p,q,ak)!=0.0)。d.x=(c1*(p.y-ak.y)-c2*(p.y-q.y)/(p.x-q.x)*(p.y-ak.y)-(p.x-ak.x)*(p.y-q

8、.y)。d.y=(c1*(p.x-ak.x)-c2*(p.x-q.x)/(p.y-q.y)*(p.x-ak.x)-(p.y-ak.y)*(p.x-q.x)。r=distance(d,ak)。elset1=distance(p,q)。t2=distance(q,ak)。t3=distance(p,ak)。5 / 8if(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=(ak.x+q.x)/2.0

9、。d.y=(ak.y+q.y)/2.0。r=distance(ak,q)/2.0。elsed.x=(ak.x+p.x)/2.0。d.y=(ak.y+p.y)/2.0。r=distance(ak,p)/2.0。void MiniDiscWithPoint(TPointpi,intn)d.x=(pi.x+a1.x)/2.0。d.y=(pi.y+a1.y)/2.0。r=distance(pi,a1)/2.0。int j 。for(j=2。j<=n。j+)if(distance(d,aj)<=r)continue。elseMiniDiscWith2Point(pi,aj,j-1) 。6 / 8int main()int i,n。while(scanf("%d",&n)&&n)for(i=1。i<=n。i+)scanf("%lf %lf",&ai.x,&ai.y)。if(n=1) printf("%.2lf %.2lf 0.00n",a1.x,a1.y) 。continue。 r=distance(a1,a2)/2.0。d.x=(a1.x+a2.x)/2.0。d.y=(a1.y+a2.y)