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

《2022年ACM计算几何最小圆覆盖算法.docx》由会员分享，可在线阅读，更多相关《2022年ACM计算几何最小圆覆盖算法.docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 步；如在第

2、4 步生成的圆的圆周只通过 A,B,C,D中的两点，就圆周上的两点取成新的 A 和 B,从另两点中任取一点作为新的 C；程序设计题解上的解题报告：对于一个给定的点集 A，记 MinCircleA 为点集 A 的最小外接圆， 明显，对于全部的点集情形A,MinCircleA 都是存在且惟一的；需要特别说明的是，当 A 为空集时， MinCircleA 为空集，当 A=a 时， MinCircleA 圆心坐标为 a，半径为 0； 明显， MinCircleA 可以有A 边界上最多三个点确定 当点集 A 中点的个数大于 1 时，有可能两个点确定了 MinCircleA ，也就是说存在着一个点集 B，

3、 |B|=3且B 包含与 A，有 MinCircleB=MinCircleA.所以，假如 a 不属于 B， 就 MinCircleA-a=MinCircleA； 如 果 MinCircleA-a不等 于欢迎下载精品学习资源MinCircleA, 就 a 属于 B； 所以我们可以从一个空集 R 开头，不断的把题目中给定的点集中的点加入 R，同时爱护 R 的外接圆最小， 这样就可以得到解决该题的算法；不断添加圆，爱护最小圆；假如添加的点 i 在圆内，不动，否就：问题转化为求 1I 的最小圆：求出 1 与 I 的最小圆，并且扫描 j=2I-1，爱护（ 1）+（i ）+2j 的最小圆，假如找到 J 不

4、在最小圆内，问题转化为：求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的最小圆上； 证明可以考虑这么做：最小圆必定是可以通过不断放大半径，直到全部以任意点为圆心，半径为半径的圆存在交点，此时的半径就是最小圆；所以上述定理可以通过这个思想得到；这个做法复杂度是 On 的，当加

5、入圆的次序随机时，由于三点定一圆，所以不在圆内概率是 3/i,求出期望可得是 On.欢迎下载精品学习资源6.最小包围圆：坐标系上 有多点 画一个最小圆 包含全部点 求出这个圆的圆心坐标和半径本人解题思路：设想一个足够大的圆 逐步缩小这个圆 并移动这个圆直到有两点在这个圆周上 假如这两点的连线不是这个圆的直径那就说明仍可以移动缩小这个圆直到显现另一个点在这个圆周上这个三个点所确定的圆就是所要求的圆；实现思路：先求出两点间的最长距离；以这两点的距离为直径画一个圆，假如 包含了全部的点那么就是所求的解；假如不能包含就说明有三点及三点在这个圆上 依据三点确定一个圆 只要枚举出全部的三点成立的圆 再比较

6、全部成立的圆的半径最小的就是所求的点；欢迎下载精品学习资源#include #include struct TPointdouble x,y；TPoint a1005,d；double r；doubledistanceTPointp1,TPointp2return sqrtp1.x-p2.x*p1.x -p2.x+p1.y-p2.y*p1.y-p2.y；double multiplyTPointp1,TPointp2,TPointp0returnp1.x-p0.x*p2.y-p0.y-p2.x-p0.x*p1.y-p0.y；void MiniDiscWith2PointTPointp,TPoi

7、ntq,intnd.x=p.x+q.x/2.0；d.y=p.y+q.y/2.0；欢迎下载精品学习资源r=distancep,q/2；int k；double c1,c2,t1,t2,t3；fork=1；k=n；k+ifdistanced,ak=t2&t1=t3d.x=p.x+q.x/2.0；d.y=p.y+q.y/2.0；r=distancep,q/2.0； else ift2=t1&t2=t3d.x=ak.x+q.x/2.0；d.y=ak.y+q.y/2.0；r=distanceak,q/2.0； elsed.x=ak.x+p.x/2.0；d.y=ak.y+p.y/2.0；r=distanc

8、eak,p/2.0；void MiniDiscWithPointTPointpi,intnd.x=pi.x+a1.x/2.0；d.y=pi.y+a1.y/2.0；r=distancepi,a1/2.0；int j；forj=2；j=n；j+ifdistanced,aj=rcontinue ；elseMiniDiscWith2Pointpi,aj,j-1；欢迎下载精品学习资源int mainint i,n；whilescanf%d,&n&nfori=1；i=n；i+scanf%lf %lf,&ai.x,&ai.y；ifn=1 printf%.2lf %.2lf 0.00n,a1.x,a1.y ；continue； r=distancea1,a2/2.0 ；d.x=a1.x+a2.x/2.0；d.y=a1.y+a2.y/2.0；fori=3；i=n；i+ifdistanced,ai=rcontinue；欢迎下载精品学习资源elseMiniDiscWithPointai,i-1；printf%.2lf %.2lf %.2lfn,d.x,d.y,r ；return 0；欢迎下载