问题6815--减少字段

6815: 减少字段

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

题目描述



【题目描述】

农民约翰的N头奶牛(3≤N≤50,000)都位于场的不同位置。FJ想用一面平行于x轴和y轴的矩形栅栏把所有的牛围起来,并且他希望这个栅栏尽可能小,这样它就能容纳每一头牛(边界上的牛是允许的)

不幸的是,由于上季度牛奶产量低,FJ的预算很紧张。因此,如果可能的话,他想建一个更小的围栏,他愿意从他的牛群中出售一头牛,以使这成为可能。

请帮助FJ计算出他从牛群中移走一头牛(然后为剩下的N - 1头牛建造最紧密的围篱)后,他可以围篱的最小面积。

对于这个问题,请将奶牛视为点,将栅栏视为四条线段的集合(也就是说,不要将奶牛视为单位正方形”)。请注意,答案可以是零,例如,如果所有剩下的奶牛最后都站在同一条垂直或水平的直线上。最后,请注意,由于N可能非常大,您可能需要小心解决这个问题,以确保您的程序运行得足够快!

输入格式】(reduce.in):

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

输出格式】(reduce.out):

写一个整数,指定FJ从他的牛群中移走一头精心挑选的牛后,能用围栏围起来的最小面积。

样例输入】:

4

2 4

1

5 2

17 25

样例输出】:

12

来源/分类