【BZOJ2338】[HNOI2011]数矩形

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long ll;int n,tot;ll ans;int x[1510],y[1510];struct node{	ll len;	int x,y,a,b;}p[2000000];bool cmp(node a,node b){	return (a.len==b.len)?((a.x==b.x)?(a.y<b.y):(a.x<b.x)):(a.len<b.len);}inline int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}ll chaji(ll x1,ll y1,ll x2,ll y2){	return x1*y2-x2*y1;}ll sqr(int a,int b,int c){	return abs(chaji(x[b]-x[a],y[b]-y[a],x[c]-x[a],y[c]-y[a]));}int main(){	n=rd();	int i,j,last,k;	for(i=1;i<=n;i++)	x[i]=rd(),y[i]=rd();	for(i=1;i<=n;i++)	{		for(j=i+1;j<=n;j++)		{			p[++tot].len=(ll)(x[i]-x[j])*(x[i]-x[j])+(ll)(y[i]-y[j])*(y[i]-y[j]);			p[tot].x=x[i]+x[j],p[tot].y=y[i]+y[j],p[tot].a=i,p[tot].b=j;		}	}	sort(p+1,p+tot+1,cmp);	for(i=1;i<=tot;i++)	{		if(p[i].len!=p[i-1].len||p[i].x!=p[i-1].x||p[i].y!=p[i-1].y)		{			for(last=i;last<=tot&&p[last].len==p[i].len&&p[last].x==p[i].x&&p[last].y==p[i].y;last++);			for(j=i;j<last;j++)	for(k=j+1;k<last;k++)	ans=max(ans,sqr(p[k].a,p[j].a,p[j].b));		}	}	printf("%lld",ans);	return 0;}//8 -2 3 -2 -1 0 3 0 -1 1 -1 2 1 -3 1 -2 1