题目大意

又是农夫约翰

有一个 $ 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 个方面去考虑：

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

算法的过程

枚举极大子矩形的左边界

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

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

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

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

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

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

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

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

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

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

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

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

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

遗漏的情况

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

第一类

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

解决方法

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

第二类

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

解决方法

预处理时增加特殊判断。

算法步骤：

1. 读入数据并记录障碍点的横纵坐标
2. 处理特殊情况，得到一个初始的 $ ans$ 值
   1. 上下为矩形边界的特殊情况
   2. 左右为矩形边界的特殊情况
3. 把障碍点先按照 \(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\) 作为右边界
4. 输出 \(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;
}