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

平面上有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)不等于MinCircle(A),则 a属于B。 所以我们可以从一个空集R开始，不断的把题目中给定的点集中的点加入R，同时维护R的外接圆最小，这样就可以得到解决该题的算法。不断添加圆，维护最小圆。如果添加的点i在圆内，不动，否则： 问题转化为求1I的最小圆：求出1与I的最小圆，并且扫描j=2I-1，维护（1）+（i）+(2j)的最小圆，如果找到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)的最小圆上。 证明可以考虑这么做：最小圆必定是可以通过不断放大半径，直到所有以任意点为圆心，半径为半径的圆存在交点，此时的半径就是最小圆。所以上述定理可以通过这个思想得到。 这个做法复杂度是O(n)的，当加入圆的顺序随机时，因为三点定一圆，所以不在圆内概率是3/i,求出期望可得是On.6.最小包围圆：坐标系上 有多点 画一个最小圆 包含所有点 求出这个圆的圆心坐标和半径本人解题思路：设想一个足够大的圆 逐渐缩小这个圆 并移动这个圆 直到有两点在这个圆周上 如果这两点的连线不是这个圆的直径 那就说明还可以移动缩小这个圆 直到出现另一个点在这个圆周上 这个三个点所确定的圆就是所要求的圆。实现思路：先求出两点间的最长距离。以这两点的距离为直径画一个圆，如果包含了所有的点那么 就是所求的解。如果不能包含就说明有三点及三点在这个圆上 根据三点确定一个圆 只要枚举出所有的三点 成立的圆 再比较所有成立的圆的半径最小的就是所求的点。#include#includestruct TPoint double x,y; ; TPoint a1005,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;r=distance(p,q)/2;int k;double c1,c2,t1,t2,t3;for(k=1;k=n;k+)if(distance(d,ak)=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;d.y=(ak.y+q.y)/2.0;r=distance(ak,q)/2.0; else d.x=(ak.x+p.x)/2.0;d.y=(ak.y+p.y)/2.0;r=distance(ak,p)/2.0;void MiniDiscWithPoint(TPoint pi,int n)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;else MiniDiscWith2Point(pi,aj,j-1);int 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