[HNOI2011]数矩形

题目描述

最近某歌手在研究自己的全球巡回演出计划，他将所有心仪的城市都用平面上的一个点来表示，并打算从中挑选出 4 个城市作为这次巡回演出的地点。

为了显示自己与众不同，他要求存在一个矩形使得挑选出的 4 个点恰好是这个矩形的 4 个顶点，并且希望这个矩形的面积最大。

这可急坏了其经纪人，于是他向全球歌迷征集方案，当然你这位歌迷一定不会错过这个机会。

输入输出格式

输入格式：

从文件input.txt中读入数据，输入文件的第一行是一个正整数 $行，每行是由空格隔开的两个整数X_iXi 和Y_iYi ,表示其对应点的坐标。20%的数据满足Nleq 500N≤500 ，100%的数据满足Nleq 1500N≤1500 ，-10^8leq X_i,Y_ileq 10^8−108≤Xi,Yi≤108 ，且输入数据保证答案存在。$

输出格式：

输出文件 output.txt 仅包含一个非负整数，表示最大的矩形面积。

输入输出样例

输入样例#1：复制

输出样例#1：复制

两条线段能作于矩形的对角线有2个条件

1.中点相同

2.长度相同

于是$O(n^{2})$处理出所有直线，排序

找到满足条件的区间，枚举得出答案

复杂度有点玄学

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long lol;
 8 struct point
 9 {
10     lol x,y;
11     lol operator *(const point &b) const
12     {
13     return x*b.y-y*b.x;
14     }
15     point operator -(const point &b) const
16     {
17     return (point){x-b.x,y-b.y};
18     }
19     point operator +(const point &b) const
20     {
21     return (point){x+b.x,y+b.y};
22     }
23 }a[1501];
24 struct Node
25 {
26     lol l;
27     point v,mid;
28 }e[2500001];
29 int n,cnt;
30 lol ans;
31 bool cmp(Node a,Node b)
32 {
33     if (a.l==b.l)
34     {
35         if (a.mid.x==b.mid.x) return a.mid.y<b.mid.y;
36      return a.mid.x<b.mid.x;
37     }
38     return a.l<b.l;
39 }
40 int main()
41 {int i,j,k,l;
42   cin>>n;
43   for (i=1;i<=n;i++)
44   {
45       scanf("%lld%lld",&a[i].x,&a[i].y);
46   }
47   for (i=1;i<=n;i++)
48   {
49     for (j=1;j<=i-1;j++)
50      {
51          e[++cnt].mid=a[i]+a[j];
52          e[cnt].v=a[i]-a[j];
53          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);
54      }
55   }
56   sort(e+1,e+cnt+1,cmp);
57   for (i=1;i<=cnt;i=j+1)
58   {
59       j=i;
60       while (j+1<=cnt&&e[j+1].l==e[i].l&&e[j+1].mid.x==e[i].mid.x&&e[j+1].mid.y==e[i].mid.y) j++;
61       for (k=i;k<=j;k++)
62       {
63           for (l=i;l<=k-1;l++)
64           {
65               ans=max(ans,abs(e[k].v*e[l].v)>>1);
66           }
67       }
68   }
69   printf("%lld",ans);
70 }