寒假每日一题——农田缩减

98 阅读 0 评论 65 点赞

我是靠谱客的博主清秀蜡烛，这篇文章主要介绍寒假每日一题——农田缩减，现在分享给大家，希望可以做个参考。

农田缩减

问题描述

农夫约翰的 N 头奶牛分布在其二维农场的不同位置。

约翰想用一个长方形的围栏把所有的奶牛围起来，围栏的边需要平行于 x 轴和 y 轴。

在能够包含所有奶牛的情况下（处于围栏边界的奶牛也算包含在内），约翰希望围栏围起的面积尽可能小。

不幸的是，由于上个季度的牛奶产量很低，约翰的预算十分紧张。

因此，他希望建立一个更小的围栏，甚至为了实现这一目标，他愿意卖掉农场中的一头奶牛。

请帮助约翰计算，卖掉牛群中的一头奶牛以后，他可以用围栏围起来的最小面积（为剩下的奶牛建造尽可能小的围栏）。

对于这个问题，请将奶牛视为点，将围栏视为四个线段的集合。

注意，答案可以是零，例如，所有剩余的奶牛最终都站在同一条垂直或水平线上。

输入格式
第一行包含整数 N。

接下来 N 行，每行包含两个整数 x,y，表示一头牛所在的位置坐标为 (x,y)。

输出格式
输出卖掉牛群中的一头奶牛以后，约翰可以用围栏围起来的最小面积。

数据范围

3≤N≤50000,

1≤x,y≤40000

输入样例：

复制代码

输出样例：

复制代码

1
2
12

思路分析

遍历所有的 nn 个奶牛位置，作为本次尝试卖掉的奶牛。取每种情况最小值，最终结果即为所求。

选择卖掉一个奶牛后，需要围栏的面积为剩余所有奶牛所围成的长方形面积，其长、宽可以分别由剩余奶牛的 x,yx,y 坐标值的最值之差得到。我们发现，如果卖掉的奶牛本身就不是上述的某一坐标最值，则卖掉它之后不会影响围栏的宽、高，也即无法减小围栏面积。所以我们只需要考虑卖掉坐标最值上的奶牛即可。

完整代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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;
}