题目描述
最近某歌手在研究自己的全球巡回演出计划，他将所有心仪的城市都用平面上的一个点来表示，并打算从中挑选出 4 个城市作为这次巡回演出的地点。
为了显示自己与众不同，他要求存在一个矩形使得挑选出的 4 个点恰好是这个矩形的 4 个顶点，并且希望这个矩形的面积最大。
这可急坏了其经纪人，于是他向全球歌迷征集方案，当然你这位歌迷一定不会错过这个机会。
输入输出格式
输入格式：
从文件input.txt中读入数据，输入文件的第一行是一个正整数NN ，表示平面上点的个数(即某歌手心仪的城市数)。接下来的NN 行，每行是由空格隔开的两个整数X_iXi 和Y_iYi ,表示其对应点的坐标。20%的数据满足N\leq 500N≤500 ，100%的数据满足N\leq 1500N≤1500 ，-10^8\leq X_i,Y_i\leq 10^8−108≤Xi,Yi≤108 ，且输入数据保证答案存在。
输出格式：
输出文件 output.txt 仅包含一个非负整数，表示最大的矩形面积。
输入输出样例
输入样例#1： 复制
8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1
输出样例#1： 复制
10
两条线段能作于矩形的对角线有2个条件
1.中点相同
2.长度相同
于是$O(n^{2})$处理出所有直线，排序
找到满足条件的区间，枚举得出答案
复杂度有点玄学
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long lol;
struct point
{
lol x,y;
lol operator *(const point &b) const
{
return x*b.y-y*b.x;
}
point operator -(const point &b) const
{
return (point){x-b.x,y-b.y};
}
point operator +(const point &b) const
{
return (point){x+b.x,y+b.y};
}
}a[];
struct Node
{
lol l;
point v,mid;
}e[];
int n,cnt;
lol ans;
bool cmp(Node a,Node b)
{
if (a.l==b.l)
{
if (a.mid.x==b.mid.x) return a.mid.y<b.mid.y;
return a.mid.x<b.mid.x;
}
return a.l<b.l;
}
int main()
{int i,j,k,l;
cin>>n;
for (i=;i<=n;i++)
{
scanf("%lld%lld",&a[i].x,&a[i].y);
}
for (i=;i<=n;i++)
{
for (j=;j<=i-;j++)
{
e[++cnt].mid=a[i]+a[j];
e[cnt].v=a[i]-a[j];
e[cnt].l=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
}
}
sort(e+,e+cnt+,cmp);
for (i=;i<=cnt;i=j+)
{
j=i;
while (j+<=cnt&&e[j+].l==e[i].l&&e[j+].mid.x==e[i].mid.x&&e[j+].mid.y==e[i].mid.y) j++;
for (k=i;k<=j;k++)
{
for (l=i;l<=k-;l++)
{
ans=max(ans,abs(e[k].v*e[l].v)>>);
}
}
}
printf("%lld",ans);
}