农田缩减
问题描述
农夫约翰的 N 头奶牛分布在其二维农场的不同位置。
约翰想用一个长方形的围栏把所有的奶牛围起来，围栏的边需要平行于 x 轴和 y 轴。
在能够包含所有奶牛的情况下（处于围栏边界的奶牛也算包含在内），约翰希望围栏围起的面积尽可能小。
不幸的是，由于上个季度的牛奶产量很低，约翰的预算十分紧张。
因此，他希望建立一个更小的围栏，甚至为了实现这一目标，他愿意卖掉农场中的一头奶牛。
请帮助约翰计算，卖掉牛群中的一头奶牛以后，他可以用围栏围起来的最小面积（为剩下的奶牛建造尽可能小的围栏）。
对于这个问题，请将奶牛视为点，将围栏视为四个线段的集合。
注意，答案可以是零，例如，所有剩余的奶牛最终都站在同一条垂直或水平线上。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含两个整数 x,y，表示一头牛所在的位置坐标为 (x,y)。
输出格式
输出卖掉牛群中的一头奶牛以后，约翰可以用围栏围起来的最小面积。
数据范围
3≤N≤50000,
1≤x,y≤40000
输入样例：
4
2 4
1 1
5 2
17 25
输出样例：
12
思路分析
遍历所有的 nn 个奶牛位置，作为本次尝试卖掉的奶牛。取每种情况最小值，最终结果即为所求。
选择卖掉一个奶牛后，需要围栏的面积为剩余所有奶牛所围成的长方形面积，其长、宽可以分别由剩余奶牛的 x,yx,y 坐标值的最值之差得到。我们发现，如果卖掉的奶牛本身就不是上述的某一坐标最值，则卖掉它之后不会影响围栏的宽、高，也即无法减小围栏面积。所以我们只需要考虑卖掉坐标最值上的奶牛即可。
完整代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int ,int> PII;
#define x first
#define y second
int n;
const int N = 50010;
const int INF = 1e18;
PII q[N];
vector<int> x, y;
int main()
{
cin >> n;
int res = INF;
for(int i = 0; i < n; i++)
{
scanf("%d%d", &q[i].x, &q[i].y);
x.push_back(q[i].x);
y.push_back(q[i].y);
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
int lenx, leny;
for(int i = 0; i < n; i++)
{
if(q[i].x == x[0]) lenx = x[n - 1] - x[1];
else if(q[i].x == x[n - 1]) lenx = x[n - 2] - x[0];
else lenx = x[n - 1] - x[0];
if(q[i].y == y[0]) leny = y[n - 1] - y[1];
else if(q[i].y == y[n - 1]) leny = y[n - 2] - y[0];
else leny = y[n - 1] - y[0];
res = min(res, lenx * leny);
}
cout << res << endl;
return 0;
}