Processing math: 100%
编程题
                ### 问题描述

小齐养了 N 头奶牛,它们分布在他二维的农场中的不同位置。小齐希望用一个矩形的围栏将所有的奶牛包围起来,使得围栏的边与 xy 轴平行,并且这个围栏要足够小,以包含每一头奶牛(允许奶牛在边界上)。

不幸的是,由于上个季度的低产,小齐的预算有限。因此,他想尽可能地建造一个更小的围栏,而且他愿意出售最多三头奶牛以实现这一目标。

请帮助小齐计算在从他的牧群中移除最多三头经过精心选择的奶牛后,他可以用围栏围住的最小面积。

对于这个问题,请将奶牛视为点,将围栏视为四条线段的集合(即不要将奶牛视为“单位正方形”)。请注意,答案可以是零,例如如果所有剩下的奶牛最终站在一个公共的垂直或水平线上。

输入格式

输入的第一行包含 N

接下来的 N 行,每行包含两个整数,表示一头奶牛的位置。奶牛的位置是范围在 140,000 的正整数。

输出格式

请输出一个整数,表示小齐在从他的牧群中移除最多三头经过精心选择的奶牛后,可以用围栏围住的最小面积。

样例输入

6
1 1
7 8
10 9
8 12
4 100
50 7

样例输出

12

评测数据规模

5N50,000

查看答案
赣ICP备20007335号-2