题目传送门

题目分析

初一看，满脸懵逼，不知如何下手，总感觉是道水题，但就是不会写。
这道题是国队大佬王知昆在2003年发表的国家集训队论文《浅谈用极大化思想解决最大子矩阵问题》中提到的2002年冬令营的一道题目。是一个比较经典的模型。
我们定义有效子矩形为内部不包含任何障碍点且边界与坐标轴平行的子矩形。如图所示，第一个是有效子矩形（尽管边界上有障碍点），第二个不是有效子矩形（因为内部含有障碍点）。

首先我们可以对所有的点按照横坐标从小到大的顺序排序，为了方便将右上角也作为一个点加进去，然后以每一个点所在的纵轴作为举矩形的左边界，并确定一个上下界，依次向后枚举每一个点作 为右边界，通过构造的矩形更新答案，以及上下边界。

如图是以点1为左边界来枚举右边界的三个阶段。可见上下边界在一直被不停地更新。

接下来我们会发现一个问题，就是答案其实并没有被完全的更新，我们漏掉了一些情况，通过上边的枚举，我们无法得到一个左边界与整个矩形的左边界完全重合的有效子矩阵以及左右边界都与整个矩阵左右边界分别重合的矩阵，及以下两种情况。


关于第一种情况，我们只需倒着枚举一边，即把所有的点作为右边界，向左枚举，就能找到左边界为矩阵左边界的情况。

对于第二种来说，我们只需要将所有的点按照纵坐标从小到大排序，那么相邻两个点之间的矩形就是如图的矩形。

代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <cmath>
# define R register
# define LL long long

using namespace std;

int l,w,n,ans;

struct pp{int x,y;}a[5010];

inline void in(R int &a){
    R char c = getchar();R int x=0,f=1;
    while(!isdigit(c)){if(c == '-') f=-1; c=getchar();}
    while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
    a = x*f;
}

inline bool cmp(R pp a,R pp b){return a.x<b.x||(a.x == b.x&&a.y<b.y);}
inline bool cmp2(R pp a,R pp b){return a.y<b.y;}

inline void maxx(R int &a,const int b){a>b? 0:a=b;}
inline void minn(R int &a,const int b){a<b? 0:a=b;}

inline int yg(){
    in(l),in(w);in(n);
    for(R int i=1; i<=n; ++i) in(a[i].x),in(a[i].y);
    a[++n] = (pp){l,w};
    sort(a+1,a+n+1,cmp);
    for(R int i=1; i<=n; ++i)
    {
        R int up = w,down = 0;
        R int j;
        for(j=i+1; j<=n; ++j)
        {
            if(a[j].y<=down||a[j].y>=up||a[j].x == a[i].x) continue;
            if((l-a[i].x)*(up-down) <= ans) break;
            maxx(ans,(a[j].x-a[i].x)*(up-down));
            if(a[j].y==a[i].y) break;
            if(a[j].y>a[i].y) minn(up,a[j].y);
            else maxx(down,a[j].y);
        }
        if(j>n) maxx(ans,(l-a[i].x)*(up-down));
    }

    for(R int i=n; i>=1; --i)
    {
        R int up = w,down = 0;
        R int j;
        for(j=i-1; j>=1; --j)
        {
            if(a[j].y<=down||a[j].y>=up||a[j].x == a[i].x) continue;
            if(a[i].x*(up-down) <= ans) break;
            maxx(ans,(a[i].x-a[j].x)*(up-down));
            if(a[j].y==a[i].y) break;
            if(a[j].y>a[i].y) minn(up,a[j].y);
            else maxx(down,a[j].y);
        }
        if(j<1) maxx(ans,a[i].x*(up-down));
    }
    sort(a+1,a+n+1,cmp2);
    for(R int i=1; i<=n; ++i)
        maxx(ans,l*(a[i].y-a[i-1].y));
    printf("%d",ans);
    return 0;
}

int youngsc = yg();
int main(){;}