AT_wupc2012_6.最後の問題

终于到了比赛当天，我到达了早稻田大学西早稻田校区。而且，我到达的时间是一个能被 $4$ 或 $7$ 整除的数字，真是个好兆头。现在我觉得无论什么题目都能解出来。

会场的教室里已经聚集了几十名学生。主办团队刚刚介绍完评测系统 AtCoder，距离比赛开始还有几分钟。我打开了带来的笔记本电脑，按捺住激动的心情，准备迎接比赛。

（那么，请开始吧！）

比赛开始了。

挑战的结果如何，以及通过比赛我得到了什么……不过，这是另一个故事，有机会再说吧。顺便说一句，这场比赛的最后一道题目如下：

在二维坐标平面上给定 $N$ 个格点。从这些点中选出 $4$ 个点组成一个长方形，编写程序求出其最大面积。长方形必须满足以下条件：

• 长方形的每条边都不能与 $x$ 轴或 $y$ 轴平行。
• 长方形的内部（不包括边）不能包含其他点。

如果除了组成长方形的 $4$ 个点以外，其他点在长方形的边上，则不算在内部。若无法构造满足条件的长方形，请输出 $0$。

输入格式如下，从标准输入读取：

$N$
$x_1\ y_1$
$x_2\ y_2$
...
$x_i\ y_i$
...
$x_N\ y_N$

• 第 $1$ 行给出点的数量 $N$，$4 \leq N \leq 10000$。
• 第 $2$ 行到第 $N+1$ 行，每行给出一个点的 $x$ 坐标和 $y$ 坐标，使用半角空格分隔。
• 对于每个 $i$，$0 \leq x_i \leq 999$ 且 $0 \leq y_i \leq 999$。
• $N$ 个点的坐标互不相同。

请输出用给定点构造的、满足条件的长方形的最大面积。如果无法构造，输出 $0$。

最后请输出换行符。

在满分 $100$ 分中，有 $10$ 分的数据满足 $N \leq 100$。

另外，有 $20$ 分的数据满足 $N \leq 1000$。

第 $1$ 行：一个整数 $N$，表示点的数量。

第 $2$ 行到第 $N+1$ 行：每行两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个点的坐标。

输出一个整数，表示满足条件的最大长方形面积。如果无法构造，输出 $0$。最后输出换行符。

无。

由 ChatGPT 4.1 翻译