包含点集所有点的最小圆的算法最小圆覆盖
http://acm.zju.edu.cn/show_problem.php?pid=1450 相关题目最小球包含
http://acm.pku.edu.cn/JudgeOnline/problem?id=2069
平面上有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的外接圆最小，这样就可以得到解决该题的算法。
zju 1450
题目描述：给定n个点，求覆盖所有点的圆的圆心和半径
#include<stdio.h>
#include<math.h>
#include<string.h>
#define MAXN 20
struct pointset{
double x, y;
};
const double precison=1.0e-8;
pointset maxcic, point[MAXN];
double radius;
int curset[MAXN], posset[3];
int set_cnt, pos_cnt;
inline double dis_2(pointset &from, pointset& to){
return ((from.x-to.x)*(from.x-to.x)+(from.y-to.y)*(from.y-to.y));
}
int in_cic(int pt){
if(sqrt(dis_2(maxcic, point[pt]))<radius+precison) return 1;
return 0;
}
int cal_mincic(){
if(pos_cnt==1 || pos_cnt==0)
return 0;
else if(pos_cnt==3){
double A1, B1, C1, A2, B2, C2;
int t0=posset[0], t1=posset[1], t2=posset[2];
A1=2*(point[t1].x-point[t0].x);
B1=2*(point[t1].y-point[t0].y);
C1=point[t1].x*point[t1].x-point[t0].x*point[t0].x+
point[t1].y*point[t1].y-point[t0].y*point[t0].y;
A2=2*(point[t2].x-point[t0].x);
B2=2*(point[t2].y-point[t0].y);
C2=point[t2].x*point[t2].x-point[t0].x*point[t0].x+
point[t2].y*point[t2].y-point[t0].y*point[t0].y;
maxcic.y=(C1*A2-C2*A1)/(A2*B1-A1*B2);
maxcic.x=(C1*B2-C2*B1)/(A1*B2-A2*B1);
radius=sqrt(dis_2(maxcic, point[t0]));
}
else if(pos_cnt==2){
maxcic.x=(point[posset[0]].x+point[posset[1]].x)/2;
maxcic.y=(point[posset[0]].y+point[posset[1]].y)/2;
radius=sqrt(dis_2(point[posset[0]], point[posset[1]]))/2;
}
return 1;
}
int mindisk(){
if(set_cnt==0 || pos_cnt==3){
return cal_mincic();
}
int tt=curset[--set_cnt];
int res=mindisk();
set_cnt++;
if(!res || !in_cic(tt)){
set_cnt--;
posset[pos_cnt++]=curset[set_cnt];
res=mindisk();
pos_cnt--;
curset[set_cnt++]=curset[0];
curset[0]=tt;
}
return res;
}
int main(){
freopen("in2.txt", "r", stdin);
freopen("radius.txt", "w", stdout);
int n;
while(scanf("%d", &n)!=EOF){
if(n==0) break;
int i;
for(i=0; i<n; i++)
scanf("%lf %lf", &point[i].x, &point[i].y);
if(n==1){
maxcic.x=point[0].x;
maxcic.y=point[0].y;
radius=0;
printf("%.2lf %.2lf %.2lf\n", maxcic.x, maxcic.y, radius);
continue;
}
set_cnt=n; pos_cnt=0;
for(i=0 ;i<n ;i++) curset[i]=i;
mindisk();
printf("%.2lf %.2lf %.2lf\n", maxcic.x, maxcic.y, radius);
}
return 0;
}
加载中，请稍候......
加载中…
喜欢