ztx's Blog

/****************************************\
* 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 ;
}

/****************************************\
* Author : ztx
* Title  : [HNOI2011]数矩形
* ALG    : 计算几何
* CMT    : 按直线中点和长度排序,再求最大矩形面积 
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [HNOI2011]数矩形
* ALG    : 计算几何
* CMT    : 按直线中点和长度排序,再求最大矩形面积 
* Time   :
\****************************************/

#include <cstdio>
#include <algorithm>

#define  maxn  1600LL

typedef long long ll ;

struct point {
	ll x , y ;
	point() {} ;
	point(ll xx , ll yy):x(xx),y(yy){}
	bool operator == (const point& b) const {
		return x==b.x && y==b.y ;
	}
	point operator - (const point& b) const {
		return point(x-b.x , y-b.y) ;
	}
	ll operator * (const point& b) const {
		return x*b.y-y*b.x ;
	}
} points[maxn] ;

struct line {
	ll len ;
	point *p1 , *p2 ;
	point midpoint ;
	bool operator < (const line& b) const {
		if (len == b.len) {
			if (midpoint.x == b.midpoint.x)
				return midpoint.y < b.midpoint.y ;
			return midpoint.x < b.midpoint.x ;
		} else return len < b.len ;
	}
} lines[maxn*maxn>>1] ;

inline ll Distance(const point& p1 , const point& p2) {
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ;
}

ll Abs(ll x) {
	return x < 0 ? -x : x ;
}

int n , tot ;
ll ans ;

int i , j ;
int main() {
	#define READ
	#ifdef  READ
		freopen("crectangle.in" ,"r",stdin ) ;
		freopen("crectangle.out","w",stdout) ;
	#endif
	scanf("%d", &n ) ;
	for (i = 1 ; i <= n ; i ++ ) {
		scanf("%lld%lld", &points[i].x , &points[i].y) ;
		for (j = 1 ; j < i ; j ++ ) {
			lines[++tot].len = Distance(points[i],points[j]) ;
			lines[tot].p1 =& points[i] ;
			lines[tot].p2 =& points[j] ;
			lines[tot].midpoint = point(points[i].x+points[j].x , points[i].y+points[j].y) ;
		}
	}
	std::sort(lines+1 , lines+tot+1) ;
	for (i = 1 ; i <= tot ; i ++ )
		for (j = i-1 ; j && lines[i].len==lines[j].len && lines[i].midpoint==lines[j].midpoint ; j -- )
			ans = std::max(ans , Abs(((*lines[i].p1)-(*lines[j].p1))*((*lines[i].p1)-(*lines[j].p2)))) ;
	printf("%lld\n", ans ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}