|
给你n个点，求一个最小的圆把所有点覆盖。 hdu3007
----------摘自顾研的《浅谈随机化思想在几何问题中的应用》
const int maxn = 508 ;
const double eps = 1e-8 ;
int dcmp(double x){
if(fabs(x) < eps) return 0 ;
if(x > 0) return 1 ;
return -1 ;
}
struct point{
double x , y ;
point(){}
point(double x , double y){
this->x = x ;
this->y = y ;
}
friend point operator - (const point &a , const point &b){
return point(a.x-b.x , a.y-b.y) ;
}
double dist(){
return sqrt(x*x + y*y) ;
}
};
/*三角形（p0 , p1 , p2）外接圆圆心cp*/
void circle_center(point p0 , point p1 , point p2 , point &cp){
double a1 = p1.x-p0.x , b1 = p1.y-p0.y , c1 = (a1*a1+b1*b1)/2 ;
double a2 = p2.x-p0.x , b2 = p2.y-p0.y , c2 = (a2*a2+b2*b2)/2 ;
double d = a1 * b2 - a2 * b1 ;
cp.x = p0.x + (c1*b2 - c2*b1) / d ;
cp.y = p0.y + (a1*c2 - a2*c1) / d ;
}
void circle_center(point p0 , point p1 , point &cp){
cp.x = (p0.x + p1.x) / 2 ;
cp.y = (p0.y + p1.y) / 2 ;
}
point center ;
double radius ;
bool point_in(const point &p){
return dcmp((p - center).dist() - radius) < 0 ;
}
int n ; point a[maxn] ;
void min_circle_cover(){
std::random_shuffle(a , a+n) ; // 打乱顺序
radius = 0 ;
center = a[0] ;
for(int i = 1 ; i < n ; i++) if(! point_in(a[i])){
center = a[i] ; radius = 0 ;
for(int j = 0 ; j < i ; j++) if(! point_in(a[j])){
circle_center(a[i] , a[j] , center) ;
radius = (a[j] - center).dist() ;
for(int k = 0 ; k < j ; k++) if(! point_in(a[k])){
circle_center(a[i] , a[j] , a[k] , center) ;
radius = (a[k] - center).dist() ;
}
}
}
}
int main(){
int i ;
while(cin>>n && n){
for(i = 0 ; i < n ; i++) scanf("%lf%lf" ,&a[i].x , &a[i].y) ;
min_circle_cover() ;
printf("%.2lf %.2lf %.2lf\n" , center.x , center.y , radius) ;
}
return 0 ;
}
洗牌函数 random_shuffle(p, p + n);
| 
转播
