P6815: 减少字段

---

【题目描述】

【题目描述】
农民约翰的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 1
5 2
17 25
【样例输出】:
12

题目类型~

USACO-2016-铜-公开赛 

咻咻~

提交答案 状态 返回