P3142 [USACO16OPEN] Field Reduction S

题目描述

Farmer John 的 $N$ 头奶牛（ $5 \leq N \leq 50,000$ ）都位于他二维牧场中的不同位置。FJ 希望用一个边平行于 $x$ 轴和 $y$ 轴的矩形围栏围住所有的奶牛，并且他希望这个围栏尽可能小，以便能够包含每头奶牛（允许奶牛位于边界上）。

不幸的是，由于上个季度牛奶产量低，FJ 的预算非常紧张。因此，他希望如果可能的话，建造一个更小的围栏，并且他愿意从他的牛群中出售最多三头奶牛来实现这一目标。

请帮助 FJ 计算在从他的牛群中移除最多三头奶牛后，他可以用围栏围住的最小可能面积（然后为剩余的奶牛建造最紧密的围栏）。

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

输入的第一行包含 $N$ 。接下来的 $N$ 行每行包含两个整数，表示一头奶牛的位置。奶牛的位置是范围在 $1 \ldots 40,000$ 的正整数。

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