/*==================================================*/ | 求最小覆盖圆 | CALL: 最小圆 = minC(Point *p,int n); /*==================================================*/ struct Point{double x,y;}; struct Circle{Point c;double r;}; double dist(Point a,Point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } Circle calc(Point p1,Point p2,Point p3){ Circle temp; double a,b,c,d,e,f; a=p2.x-p1.x; b=p2.y-p1.y; c=(p2.x*p2.x+p2.y*p2.y-p1.x*p1.x-p1.y*p1.y)/2; d=p3.x-p1.x; e=p3.y-p1.y; f=(p3.x*p3.x+p3.y*p3.y-p1.x*p1.x-p1.y*p1.y)/2; temp.c.y=(c*d-f*a)/(b*d-e*a); temp.c.x=(c*e-f*b)/(a*e-b*d); return temp; } Circle minC(Point *p,int n){ Circle O; int i,j,k; O.c=p[0];O.r=0; for(i=1;i<n;i++){ if(dist(O.c,p[i])<=O.r+1e-6)continue; O.c=p[i];O.r=0; for(j=0;j<i;j++){ if(dist(O.c,p[j])<=O.r+1e-6)continue; O.c.x=(p[i].x+p[j].x)/2;O.c.y=(p[i].y+p[j].y)/2;O.r=dist(O.c,p[j]); for(k=0;k<j;k++){ if(dist(O.c,p[k])<=O.r+1e-6)continue; O=calc(p[i],p[j],p[k]); O.r=dist(O.c,p[k]); } } } return O; }
