题目描述

农夫约翰的N头奶牛（3 ≤ N ≤ 50,000）分布在二维牧场的不同位置。约翰想用平行于x轴和y轴的矩形围栏包围所有奶牛，并希望围栏尽可能小（允许奶牛在边界上）。

由于上季度牛奶产量低，约翰预算紧张。他愿意卖掉一头牛，使得剩下的N-1头牛能被更小的围栏包围。请计算移除一头牛后，剩余牛群的最小包围面积。

注意：

• 奶牛视为点，围栏由四条线段组成
• 答案可能为0（如剩余奶牛在同一直线上）
• 需要考虑算法效率以处理大规模数据

输入格式

第一行：整数N

接下来N行：每行两个整数表示奶牛坐标（1 ≤ x,y ≤ 40,000）

输出格式

一个整数，表示移除一头牛后的最小包围面积

输入输出样例

输入 #1

4
2 4
1 1
5 2
17 25

输出 #1

12

样例解释

原始4头牛的最小包围矩形面积为(17-1)×(25-1)=384

移除最优选择：

1. 若移除(2,4)：新面积(17-1)×(25-1)=384
2. 若移除(1,1)：新面积(17-5)×(25-2)=276
3. 若移除(5,2)：新面积(17-1)×(25-1)=384
4. 若移除(17,25)：新面积(5-1)×(4-1)=12

因此最优解是移除(17,25)，最小面积为12

解题思路

1. 预处理所有奶牛的x/y极值（min_x, max_x, min_y, max_y）
2. 找出对每个极值贡献最大的奶牛（即移除该牛能最大程度缩小对应边界）
3. 检查移除以下四种候选牛后的面积：
   • 贡献min_x的牛
   • 贡献max_x的牛
   • 贡献min_y的牛
   • 贡献max_y的牛
4. 取这四种情况中的最小面积

时间复杂度：O(N)（只需线性扫描处理极值）