/****************************************\
* Author : ztx
* Title  : [ZOJ1450]最小圆覆盖
* ALG    : 计算几何
* CMT    : 最小圆覆盖模板题
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [ZOJ1450]最小圆覆盖
* ALG    : 计算几何
* CMT    : 最小圆覆盖模板题
* Time   :
\****************************************/

#include <cstdio>
#include <algorithm>
#include <cmath>

#define  maxn  110LL

struct point {
	double x , y ;
} points[maxn] , c ;

int n ;

inline double Distance(const point& a , const point& b) {
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)) ;
}

point Circumcenter(point& a , point& b , point& c) {
	point ret ;
	double a1 = b.x-a.x , b1 = b.y-a.y , c1 = (a1*a1+b1*b1)/2 ;
	double a2 = c.x-a.x , b2 = c.y-a.y , c2 = (a2*a2+b2*b2)/2 ;
	double d = a1*b2-a2*b1 ;
	ret.x = a.x+(c1*b2-c2*b1)/d ;
	ret.y = a.y+(a1*c2-a2*c1)/d ;
	return ret ;
}

int i , j , k ;
double r ;
void Solve() {
	std::random_shuffle(points , points+n) ;
	c = points[0] ; r = 0 ;/* 注意c和r的初始化 */
	for (i = 1 ; i < n ; i ++ ) {
		if (Distance(points[i] , c) <= r) continue ;
		c = points[i] ; r = 0 ;
		for (j = 0 ; j < i ; j ++ ) {
			if (Distance(points[j] , c) <= r) continue ;
			c.x = (points[i].x+points[j].x)/2 ;
            c.y = (points[i].y+points[j].y)/2 ;
            r = Distance(points[j] , c) ;
            for (k = 0 ; k < j ; k ++ ) {
                if (Distance(points[k] , c) <= r) continue ;
                c = Circumcenter(points[i] , points[j] , points[k]) ;
                r = Distance(points[i] , c) ;
            }
		}
	}
	printf("%.8lf %.8lf %.8lf\n", c.x , c.y , r) ;
}

int main() {
	#define READ
	#ifdef  READ
		freopen("minimalcircle.in" ,"r",stdin ) ;
		freopen("minimalcircle.out","w",stdout) ;
	#endif
	int i ;
	while (scanf("%d",&n) , n) {
		for (i = 0 ; i < n ; i ++ )
			scanf("%lf%lf", &points[i].x , &points[i].y) ;
		Solve() ;
    }
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

• 相关文章
• 全局相关文章