最大子矩形

在一个图形中找到它的最大子矩形，是一类很经典的问题。通常是要求在一个大的区域内，有一些特殊点，要求找到区域内不包含特殊点的最大矩形。

这种问题根据数据的特征可以分为两类：区域小，特殊点多；区域大，特殊点少。

区域小，特殊点多的情况，可以开一个二维数组存图，利用“悬线法”解决；区域大，特殊点少的情况，由于区域大，二维数组存不下，可以对于每个点从左向右（从上到下）枚举它的右（左）边界来解决。总的来说，解决“最大子矩形”的问题，往往从“极大子矩形”的特征入手（必须包括了一条完整的悬线，边界上一定有特殊点），进而枚举出所有的极大子矩形，找到最大的极大子矩形，即可求解出最大子矩形。

所谓极大子矩形，是指四条边都无法再向外扩张的矩形。

P4147

这道题目中，我们竖着看一条一条的区域，可以把它们看作一条一条的“悬线”。不难发现，“极大子矩形”内一定有一根完整的“悬线”。因为，假设矩形内所有的悬线都是不完整的，那么我们至少可以将它们向上“抬一格”，所以它不是极大子矩形。那么我们想要枚举所有的极大子矩形，不妨找到所有悬线对应的最大矩形，即，对于每一根悬线，将它向左向右平移，得到一个极大矩形区域，求解出它的面积即可。由于它的高已知（就是悬线的长度），如何求解它的宽呢？只需要预处理出每个点左右边最近的障碍在哪里，然后对于每根悬线，遍历悬线上的所有点即可找到左右边界。

P1578

不难发现，极大子矩形四条边上至少存在一个障碍点,且其他边所在直线必须都经过障碍点或与边界重合。

我们枚举每个在矩形上的点，假设它在矩形的左边上，再遍历所有可能的右边界（在矩形左边的右侧的点所在的竖线），在遍历的过程中不断维护更新上下边界的高度，即可遍历所有“障碍点位于矩形的左右边界”的情况；同理从上到下枚举遍历一遍可以遍历所有“障碍点位于矩形的上下边界”的情况。另外，对于极大子矩形边与大矩形边界重合的情况，不妨在最初将大矩形的四个角都加入到点集当中，可以使这种情况也考虑完备。

#include <algorithm>
#include <iostream>
using namespace std;
#define pii pair<int, int>
#define ma(x, y) ((x) > (y) ? (x) : (y))
#define mi(x, y) ((x) < (y) ? (x) : (y))
const int maxn = 5e3 + 15;
int l, w, n, res;
pii a[maxn];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> l >> w >> n;
    for (int i = 0, x, y; i < n; i++) {
        cin >> x >> y;
        a[i] = {x, y};
    }
    a[n++] = {0, 0}, a[n++] = {0, w}, a[n++] = {l, 0}, a[n++] = {l, w};
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        int up = w, down = 0;
        for (int j = i + 1; j < n; j++) {
            res = max(res, (a[j].first - a[i].first) * (up - down));
            if (a[j].second >= a[i].second) {
                up = min(up, a[j].second);
            }
            if (a[j].second <= a[i].second) {
                down = max(down, a[j].second);
            }
        }
    }
    sort(a, a + n, [](pii x, pii y) {
        return x.second < y.second;
    });
    for (int i = 0; i < n; i++) {
        int left = 0, right = l;
        for (int j = i + 1; j < n; j++) {
            res = max(res, (a[j].second - a[i].second) * (right - left));
            if (a[j].first >= a[i].first) {
                right = min(right, a[j].first);
            }
            if (a[j].first <= a[i].first) {
                left = max(left, a[j].first);
            }
        }
    }
    cout << res;
    return 0;
}