题目描述
【题目描述】
农夫John的N头奶牛(5≤N≤50,000头)都位于他的二维牧场中的不同位置。FJ想用一个矩形的栅栏把所有的奶牛围起来,栅栏的两边平行于x轴和y轴,他希望这个栅栏尽可能小,以容纳所有奶牛(允许边界上有奶牛)。
不幸的是,由于上个季度牛奶产量低,FJ的预算紧张。因此,如果可能的话,他想建造一个更小的围栏,并且他愿意卖掉牛群中的三头牛,以实现这一目标。
请帮助FJ计算在从牛群中移走最多三头奶牛后,他可以用围栏围起来的最小面积(然后为剩余的奶牛建立最紧密的围栏)。
对于这个问题,请将奶牛视为点,将围栏视为四条线段的集合(即,不要将奶牛视为“单位正方形”)。请注意,答案可以是零,例如,如果所有剩余的奶牛最终站在一条共同的垂直或水平线上。
【输入格式】(reduce.in):
第一行输入一个整数N,接下来的N行每一行包含两个整数,指定奶牛的位置。牛的位置是1…40,000范围内的正整数。
【输出格式】(reduce.out):
输出一个整数,指定FJ从他的牛群中移走最多三头精心挑选的奶牛后,可以用围栏围起来的最小面积。
【样例输入】:
6
1 1
7 8
10 9
8 12
4 100
50 7
样例输出:
12