#2338. [HNOI2011]数矩形

[HNOI2011]数矩形

题目描述

最近某歌手在研究自己的全球巡回演出计划,他将所有心仪的城市都用平面上的一个点来表示,并打算从中祧选出 44 个城市作为这次巡回演出的地点。为了显示自己与众不同,他要求存在一个矩形使得选出的 44 个点恰好是这个矩形的 44 个顶点,并且希望这个矩形的面积最大。这可急坏了其经纪人,于是他向全球歌迷征集方案,当然你这位歌迷一定不会错过这个机会。

输入格式

输入的第一行是一个正整数 nn,表示平面上点的个数(即某歌手心仪的城市数)。接下来的 nn 行,每行是由空格隔开的两个整数 xix_iyiy_i,表示其对应点的坐标。

输出格式

一个非负整数,表示最大的矩形面积。

8
-2 -3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1
10

数据规模与约定

对于 20%20\% 的数据,n500n\le500
对于 100%100\% 的数据,n1500n\le1500108xi,yi108-10^8\le x_i,y_i\le10^8。且输入数据保证答案存在。