← 返回题目列表

AtCoder · wupc2012_6

F. 最后一个问题

中文机器翻译题面 查看原题
 比赛终于到来的那天,我抵达了早稲田大学·西早稲田校区。而且,我到达的时间是能被4和7整除的数字。这非常吉利。现在感觉无论什么问题都能解决。
 会场的教室里已经聚集了数十名学生。运营团队讲解完了裁判系统和AtCoder,再过几分钟比赛就要开始了。我展开了带来的笔记本型计算器,按捺着跳动的心脏,为比赛做准备。

 (那么,请开始吧!)

 然后,比赛开始了。

 挑战的结果如何,以及通过比赛我得到了什么呢……不过,这是另一个故事。有机会再讲吧。顺便说一下,这次比赛出的最后一道题目,是如下内容。

問題文

 在二维坐标平面上有格点 N 个给出。从这些点中选出 4 个点组成矩形时,编写程序求其最大面积。不过,矩形必须满足以下条件:
     
  • 矩形的每条边 x 轴或 y 必须与坐标轴平行。
  •  
  • 矩形内部(不包括边)不得包含其他点。
除组成矩形的4点以外的点在边上时视为不在内部。如果无法构成满足条件的矩形时,0 。
图1:满足条件的矩形示例
图2:不满足条件的矩形示例。矩形的边必须与坐标轴平行。
图3:不满足条件的矩形示例。矩形内部不得包含其他点。

入力

输入是按以下格式从标准输入给出的。
N
x_{1} y_{1}
x_{2} y_{2}
...
x_{i} y_{i}
...
x_{N} y_{N}
  • 1 行表示点的数量 N(4 ≦ N ≦ 10000).
  • 2 行目〜N+1行表示每个点的 x 坐标和 y 坐标以半角空格分隔。
  • 各 i 关于 0 ≦ x_{i} ≦ 999 和 0 ≦ y_{i} ≦ 999 很满意。
  • N 所有点的坐标都不相同。

出力

使用给定的点构造满足条件的矩形时,请在一行中输出其最大面积。如果没有一个矩形能够满足条件,0 。
注意,最后要输出换行符。

部分点

在满分100分中,有10分是,N ≦ 100 很满意。
另外,在20分中,N ≦ 1000 很满意。

入力例 1

4
0 0
1 0
0 1
1 1

出力例 1

1
  • 4 可以选择点来构造矩形,其面积为 1 是。

入力例 2

5
0 0
2 0
0 2
2 2
1 1

出力例 2

0
  • (0,0),(0,2),(2,2),(2,0) 可以得到第 4 可以选择点来构造矩形,但这个矩形由于内部包含 (1,1) ,所以不满足条件。给定的 5 点无法构造满足条件的矩形,因此,0 。 你只需要砍掉

入力例 3

6
0 0
1 0
2 0
0 1
0 2
2 2

出力例 3

4
  • (0,0),(0,2),(2,2),(2,0) 可以得到第 4 可以选择点来构造矩形。请注意,边上可以有其他点重合。