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

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