包含點集所有點的最小圓的算法最小圓覆蓋 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;
}