C++11(clang++ 3.9) 解法, 执行用时: 321ms, 内存消耗: 29688K, 提交时间: 2019-03-16 10:41:07

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void qmax(ll &x,ll y) {if (x<y) x=y;}
void qmin(ll &x,ll y) {if (x>y) x=y;}
inline int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(isdigit(s)) {k=k*10+(s^'0');s=getchar();}
    return k*base;
}
inline void write(int x)
{
    static char cnt,num[15];cnt=0;
    if (!x)
    {
        putchar('0');
        return;
    }
    for (;x;x/=10) num[++cnt]=x%10;
    for (;cnt;putchar(num[cnt--]+48));
}
const int maxn=1550;
const int maxm=1500*(1500-1)/2+5;
int n,id,sum;
struct node
{
    int x,y;
} a[maxn];
struct node1
{
    int a,b;
    node mid;
    ll dis;
} b[maxm];
int r[maxm];
ll ans;
ll dis(node aa,node bb)
{//求两点之间的距离
    return (ll)(aa.x-bb.x)*(aa.x-bb.x)+(ll)(aa.y-bb.y)*(aa.y-bb.y);
}
ll qs(node a1,node a2,node b1,node b2)//求矩形面积，a1,a2在一条对角线上
{
    ll s1=max(abs(a1.x-a2.x),abs(b1.x-b2.x));
    s1=s1*(ll)max(abs(a1.y-a2.y),abs(b1.y-b2.y));
    s1=s1-(ll)abs(a1.x-b1.x)*abs(a1.y-b1.y);
    s1=s1-(ll)abs(a2.x-b1.x)*abs(a2.y-b1.y);
    return s1;
}
bool cmp(node1 aa,node1 bb)
{
    if (aa.dis!=bb.dis) return aa.dis>bb.dis;
    if (aa.mid.x!=bb.mid.x) return aa.mid.x<bb.mid.x;
    return aa.mid.y<bb.mid.y;
}
int main()
{
#ifdef ylx
    freopen("p3217.in","r",stdin);
    freopen("p3217.out","w",stdout);
#endif
    n=read();
    for (int i=1;i<=n;i++)
    {
        a[i].x=read();a[i].y=read();
    }
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
        {
            ++id;
            b[id].a=i,b[id].b=j;
            b[id].mid.x=a[i].x+a[j].x;
            b[id].mid.y=a[i].y+a[j].y;//避免精度误差所以没有/2
            b[id].dis=dis(a[i],a[j]);
        }
    sort(b+1,b+id+1,cmp);
    sum=1;
    for (int i=1;i<=id;)
    {//不同种的分开
        while (i==1||(b[i].dis==b[i-1].dis&&b[i].mid.x==b[i-1].mid.x&&b[i].mid.y==b[i-1].mid.y)) i++;
        r[sum]=i-1;i++;
        sum++;
    }
    for (int j=1;j<=sum;j++)
    {//枚举
        for (int i=r[j-1]+1;i<r[j];i++)
            for (int k=i+1;k<=r[j];k++)
            {
                qmax(ans,qs(a[b[i].a],a[b[i].b],a[b[k].a],a[b[k].b]));
            }
    }
    printf("%lld\n",ans);
    return 0;
}