问题 5915 --NOI2011湖北省选 二试 第3题 数矩形

5915: NOI2011湖北省选 二试 第3题 数矩形

时间限制: 2 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

最近某歌手在研究自己的全球巡回演出计划,他将所有心仪的城市都用平面上的一个点来表示,并打算从中挑选出4个城市作为这次巡回演出的地点。为了显示自己与众不同,他要求存在一个矩形使得挑选出的4个点恰好是这个矩形的4个顶点,并且希望这个矩形的面积最大。这可急坏了其经纪人,于是他向全球歌迷征集方案,当然你这位歌迷一定不会错过这个机会。 【输入格式】(input.txt)
从文件input.txt中读入数据,输入文件的第一行是一个正整数N,表示平面上点的个数(即某歌手心仪的城市数)。接下来的N行,每行是由空格隔开的两个整数Xi和Yi,表示其对应点的坐标。20%的数据满足N≤500,100%的数据满足N≤1500,-108≤Xi,Yi≤108,且输入数据保证答案存在。

输入

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

输出

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

样例输入

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

样例输出

10

来源

 

[提交][状态]