题目大意

~~又是农夫约翰~~

有一个 $ L \times W$ 的矩阵，中间有 $ n $ 个障碍，你要框出面积最大的一块长方形，其中不能包含障碍。

数据范围

对于所有数据， $0 \le n \le 5 \times 10^3，1 \le L,W \le 3 \times 10^4$

题解

首先，可以根据极大化思想设计一个基本算法：

枚举上下左右四个边界，然后判断组成的矩形是否是有效子矩形。

时间复杂度：$ O \left( S ^ 5\right)$

初步改进算法

算法：枚举左右边界，然后对处在边界内的点排序。

每两个相邻的点和左右边界一起组成一个矩形。

复杂度： $ O \left( S ^ 3\right)$

可以改进的地方：枚举了部分不是极大子矩形的情况

进一步改进算法

从下面 2 个方面去考虑：

保证每一个枚举的子矩形都是有效的
保证每一个枚举的子矩形都是极大的

算法的过程

枚举极大子矩形的左边界

$\to$ 根据确定的左边界，找出相关的极大子矩形

$ \to $ 检查和处理遗漏的情况

首先，将所有障碍点按横坐标从小到大的顺序将点标为 $1$ 号点，$2$ 号点……

为了处理方便，在矩形的四个顶点上各增加 $1$ 个障碍点。

第一次取 $1$ 号点作为所要枚举的极大子矩形的左边界

设定上下边界为矩形的上下边界

从左向右扫描，第一次遇到 $2$ 号点，可以得到一个有效的极大子矩形

因为左边界覆盖 1 号点且右边界在 2 号点右边的有效子矩形都不能包含 2 号点，

所以需要修改上下边界,2 号点在 1 号点上方，因此要修改上边界

继续扫描到 $3$ 号点，又得到一个极大有效子矩形，如图所示

因为 $3$ 号点在 $1$ 号点下方，所以要修改下边界。

然后将左边界移动到 $2$ 号点、$3$ 号点……横坐标的位置。

开始扫描以 $2$ 号点、$3$ 号点……为左边界的极大子矩形。

遗漏的情况

前面的做法可以找出所有左边界覆盖了一个障碍点的极大子矩形，此外，还有两类遗漏的情况。

第一类

左边界与整个矩形的左边界重合，右边界覆盖一个障碍点的情况。

解决方法

用类似的方法从右向左扫描一次。

第二类

是左边界与整个矩形的左边界重合，且右边界也与整个矩形的右边界重合的情况。

解决方法

预处理时增加特殊判断。

算法步骤：

读入数据并记录障碍点的横纵坐标
处理特殊情况，得到一个初始的 $ ans$ 值
1. 上下为矩形边界的特殊情况
2. 左右为矩形边界的特殊情况
把障碍点先按照 $x$ 从小到大排序，$x$ 相同时 $y$ 从小到大
1. 从左到右枚举每个障碍点 $i$ 作为左边界
  1. 初始化 $L = 0;R = Wide;maxL = Len - a[i].x$
  2. 从左到右扫描其他障碍点 $j$
    1. 最优性剪枝 $if((R-L)*maxL \le Ans) break;$
    2. 若此点在上边界上方或下边界下方或与 $i$ 点在同一列，则 $continue$
    3. 计算比较 $Ans = \max(Ans,(R - L) \times (a[j].x - a[i].x))$
    4. 若 $i$ 与 $j$ 处在同一行则退出，因为上下边界重合后后面的点无影响
    5. 修改上下边界
  3. 从右到左枚举每个障碍点 $i$ 作为右边界
输出 $Ans$

代码

#include<bits/stdc++.h>
#define N 50010
using namespace std;
struct node{
	int x,y;
}a[N];
int l,w,n,b[N],c[N],ans = 0;
bool cmp(node a,node b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
int main(){
	scanf("%d%d%d",&l,&w,&n);
	for(int i = 1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
		b[a[i].x] = 1,c[a[i].y] = 1;
	}
	b[0] = 1,c[0] = 1;a[++n].x = 0,a[n].y = 0;
	b[l] = 1,c[w] = 1;a[++n].x = l,a[n].y = w;
	a[++n].x = l,a[n].y = 0;
	a[++n].x = 0,a[n].y = w;
	sort(a+1,a+n+1,cmp);
	int maxl,last = 0,lt,rt,j;
	for(int i = 1;i<=l;i++){
		if(!b[i]) continue;
		ans = max(ans,w*(i-last));
		last = i;
	}
	last = 0;
	for(int i = 1;i<=w;i++){
		if(!c[i]) continue;
		ans = max(ans,l*(i-last));
		last = i;
	}
	for(int i = 1;i<=n;i++){
		lt = 0,rt = w,maxl = l-a[i].x;
		if(maxl*(rt-lt)<ans) break;
		for(j = i+1;j<=n;j++){
			if(a[j].y<lt||a[j].y>rt||a[i].x==a[j].x)continue;
			ans = max(ans,(rt-lt)*(a[j].x-a[i].x));
			if(a[j].y==a[i].y) break;
			if(a[j].y<a[i].y) lt = max(lt,a[j].y);
			else  rt = min(rt,a[j].y);
		}
		if(j>n) ans = max(ans,(rt-lt)*(l-a[i].x));
	}
	for(int i = n;i>=1;i--){
		lt = 0,rt = w,maxl = a[i].x;
		printf("%d\n",maxl*(rt-lt));
		if(maxl*(rt-lt)<ans) break;
		for(j = i-1;j>=1;j--){
			if(a[j].y<lt||a[j].y>rt||a[i].x==a[j].x)continue;
			ans = max(ans,(rt-lt)*(a[i].x-a[j].x));
			if(a[j].y==a[i].y) break;
			if(a[j].y<a[i].y) lt = max(lt,a[j].y);
			else  rt = min(rt,a[j].y);
		}
		if(j<1) ans = max(ans,(rt-lt)*a[i].x);
	}
	printf("%d",ans);
	return 0;
}