HNOI2011 数矩形（计算几何）

发表于 |
字数统计: 688字 | 阅读时长 ≈ 3min

【HNOI2011】数矩形

问题描述

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

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

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

输入格式

第一行是一个正整数N，表示平面上点的个数（即某歌手心仪的城市数）。

接下来N行，每行是两个整数Xi,Yi，表示对应点的坐标。

输出格式

输出一个数，表示最大矩形面积。

样例输入

8

-2 3

-2 -1

0 3

0 -1

1 -1

2 1

-3 1

-2 1

样例输出

10

提示

$1<=N<=1500 , -10^8<=Xi,Yi<=10^8$

求矩形数量，枚举对角线，先暴力计算两点连线长度和中点，然后将这些存到结构体里面按中点坐标和长度排序。

两条对角线要构成矩形必须满足中点重合且长度相等，排完序后暴力往前找符合条件的边就行了。想一想就能发现暴力找并不会被卡，因此复杂度就是$O(n^2\log n)$的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 10000000
#define ll long long
using namespace std;
struct node{ll x1,y1,x2,y2,xmid,ymid,len;}L[N];
bool operator<(node a,node b)
{
	if(a.len!=b.len)return a.len<b.len;
	if(a.xmid!=b.xmid)return a.xmid<b.xmid;
	return a.ymid<b.ymid;
}
bool operator==(node a,node b)
{
	if(a.len!=b.len)return 0;
	if(a.xmid!=b.xmid)return 0;
	if(a.ymid!=b.ymid)return 0;
	return 1;
}
ll n,X[N],Y[N],tot,ans;
ll Gdis(ll a,ll b)
{
	ll x=X[a]-X[b];
	ll y=Y[a]-Y[b];
	return x*x+y*y;
}
ll Garea(ll a,ll b)
{
	ll x1=L[a].x1-L[b].x1;
	ll x2=L[a].x2-L[b].x1;
	ll y1=L[a].y1-L[b].y1;
	ll y2=L[a].y2-L[b].y1;
	return abs(x1*y2-x2*y1);
}
int main()
{
	ll i,j,k,x,y;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)scanf("%lld%lld",&X[i],&Y[i]);
	for(i=1;i<=n;i++)
	for(j=1;j<i;j++)L[++tot]=(node){X[i],Y[i],X[j],Y[j],X[i]+X[j],Y[i]+Y[j],Gdis(i,j)};
	sort(L+1,L+tot+1);
	for(i=2;i<=tot;i++)
	for(j=i-1;j>=1&&L[i]==L[j];j--)
	ans=max(ans,Garea(i,j));
	printf("%lld",ans);
}