问题6955--牧场栅栏

6955: 牧场栅栏

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

【题目描述】

农夫JohnN头奶牛(5N50,000)都位于他的二维牧场中的不同位置。FJ想用一个矩形的栅栏把所有的奶牛围起来,栅栏的两边平行于x轴和y轴,他希望这个栅栏尽可能小,以容纳所有奶牛(允许边界上有奶牛)。

不幸的是,由于上个季度牛奶产量低,FJ的预算紧张。因此,如果可能的话,他想建造一个更小的围栏,并且他愿意卖掉牛群中的三头牛,以实现这一目标。

请帮助FJ计算在从牛群中移走最多三头奶牛后,他可以用围栏围起来的最小面积(然后为剩余的奶牛建立最紧密的围栏)

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

【输入格式】(reduce.in:

第一行输入一个整数N,接下来的N行每一行包含两个整数,指定奶牛的位置。牛的位置是140,000范围内的正整数。

【输出格式】(reduce.out):

输出一个整数,指定FJ从他的牛群中移走最多三头精心挑选的奶牛后,可以用围栏围起来的最小面积。

【样例输入】:

6

1 1

7 8

10 9

8 12

4 100

50 7

样例输出:

12

来源/分类