Field Reduction

题目描述

农夫约翰有 $N$ 头奶牛（$5 \leq N \leq 50,000$），它们都位于他二维牧场中互不相同的位置。FJ 想用一个边与 $x$、$y$ 轴平行的矩形栅栏把所有奶牛围起来，并且希望这个栅栏尽可能小，使其包含每一头奶牛（允许奶牛位于边界上）。

不幸的是，由于上一季度产奶量低，FJ 的预算很紧。因此，如果可能的话，他希望建造一个更小的围栏区域，并愿意从牛群中卖掉最多三头奶牛来实现这一点。请帮助 FJ 计算：从牛群中移除最多三头奶牛后（并为剩余奶牛建造最紧的包围栅栏），他能用栅栏围出的最小可能面积。

在本题中，请将奶牛视为点，将栅栏视为由四条线段组成（即不要把奶牛看作“单位正方形”）。注意答案可以为零，例如如果剩下的所有奶牛最终都站在同一条竖直线或水平线上。

输入格式

输入格式（文件 reduce.in）： 第一行输入包含 $N$。接下来 $N$ 行每行包含两个整数，表示一头奶牛的位置。奶牛位置为正整数，范围在 $1 \ldots 40,000$。

输出格式

输出格式（文件 reduce.out）： 输出一个整数，表示在移除最多三头精心挑选的奶牛后，FJ 能用栅栏围出的最小面积。

6
1 1
7 8
10 9
8 12
4 100
50 7

12

提示

题目鸣谢：Brian Dean

标签: USACO|2016|Silver

来源

USACO|2016|Silver