正方形鱼池题解-526互联

首先这道题\(T\)的范围很小，而\(N\)的范围却很大，所以我们只能枚举树
那么我们如何枚举呢，树有上下左右之分，看起来十分难枚举，现在让我们仔细分析一下：

水池的边长就等于\(min(上下界的距离，左右界的距离)\)

这时我们就可以开始枚举了，我枚举的是左右界

那么我们此时就可以发现上下界的两颗树一定在左右两颗树之间

为什么？

如图，如果说上下界在红色点的话，我们完全可以以这两个点为左右界，因为它们之间的距离显然更长

接下来我们就开始枚举了

第一步，按照\(x\)进行排序

第二步，初始化上下边界为墙，防止没有

第三步，两重循环，枚举所有树，再用两个变量存储上下界，注意\(j\)是\(i+1\)，因为需要枚举左右边界，如果中间还有一个就不行了

枚举上下界如图

此时我们可以发现还有几种情况没有考虑，这里只解决了上下界至少有一棵树的情况

我们需要分类讨论：

两界或三界有墙（如样例1）

我们可以进行转化

手动种树，就可以变成之前的情况了，注意我们要在坐标0种树，因为题目从1开始，这样正好提供了便利，不从0开始会漏掉

左右界至少有一棵树

我们根据上下界至少有一棵树的方式类推就可以了

ac代码

#include <bits/stdc++.h>
using namespace std;

const int MAXT = 105;
int n, t;
struct node {
    int x, y;
} tree[MAXT];

bool cmp1(node a, node b) { return a.x < b.x; }

bool cmp2(node a, node b) { return a.y < b.y; }

int main() {
    scanf("%d%d", &n, &t);
    n++;
    for (int i = 1; i <= t; i++) scanf("%d%d", &tree[i].x, &tree[i].y);
    //四角种树
    tree[++t] = { 0, 0 }, tree[++t] = { 0, n };
    tree[++t] = { n, n }, tree[++t] = { n, 0 };
    //枚举左右界
    sort(tree + 1, tree + 1 + t, cmp1);
    int ans = 0;
    for (int i = 1; i <= t; i++) {
        int minn = 1, maxn = n;
        for (int j = i + 1; j <= t; j++) {
            if (maxn - minn - 1 < tree[j].x - tree[i].x - 1)
                break;
            ans = max(ans, tree[j].x - tree[i].x - 1);
            if (tree[j].y <= tree[i].y)
                minn = max(minn, tree[j].y);
            if (tree[j].y >= tree[i].y)
                maxn = min(maxn, tree[j].y);
        }
    }
    //枚举上下界
    sort(tree + 1, tree + 1 + t, cmp2);
    for (int i = 1; i <= t; i++) {
        int minn = 1, maxn = n;
        for (int j = i + 1; j <= t; j++) {
            if (maxn - minn - 1 < tree[j].y - tree[i].y - 1)
                break;
            ans = max(ans, tree[j].y - tree[i].y - 1);
            if (tree[j].x <= tree[i].x)
                minn = max(minn, tree[j].x);
            if (tree[j].x >= tree[i].x)
                maxn = min(maxn, tree[j].x);
        }
    }
    cout << ans;

    return 0;
}