|
题目大意：给定n个点，求一个最大的矩形，该矩形的四个顶点在给定的点上
找矩形的方法是记录所有线段 若两条线段长度相等且中点重合 这两条线段就可以成为矩形的对角线
于是我们找到所有n*(n-1)/2条线段，按长度排序，长度相等按照中点排序，然后对于每个点向前找符合要求的，计算面积，更新ans
注意避免一切double！长度切记不能开根号，直接用long long存储，否则第三个点有两条长度极其接近的线段把double卡掉，计算面积要用叉积，中点不要除以2，连math库都不用开了！
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1600
using namespace std;
typedef long long ll;
struct point{
ll x,y;
point(){}
point(ll _,ll __):x(_),y(__){}
bool operator == (const point &Y) const
{
return x==Y.x && y==Y.y ;
}
point operator - (const point &Y) const
{
return point(x-Y.x,y-Y.y);
}
ll operator * (const point &Y) const
{
return x*Y.y-Y.x*y;
}
}points[M];
struct line{
ll len;
point *p1,*p2;
point midpoint;
bool operator < (const line &y) const
{
if( len == y.len )
{
if( midpoint.x == y.midpoint.x )
return midpoint.y < y.midpoint.y;
return midpoint.x < y.midpoint.x;
}
return len < y.len;
}
}lines[M*M>>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 lllabs(ll x)
{
return x<0?-x:x;
}
int n,tot;
ll ans;
int main()
{
int i,j;
cin>>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);
}
}
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=max( ans , lllabs( ( (*lines[i].p1)-(*lines[j].p1) )*( (*lines[i].p1)-(*lines[j].p2) ) ) );
cout<<ans<<endl;
}
| 
转播
