P1578 奶牛浴场

题面链接

最大子子矩形问题

首先一些概念

1.有效子矩阵： 内部不包含任何障碍点，且边界与坐标轴平行的子矩阵

2.极大子矩阵：一个有效子矩阵，如果不包含它，且比它大的有效子矩阵，则为极大有效子矩阵

3.最大有效子矩阵：所有有效矩阵中最大面积的子矩阵

极大化思想

定理1. 有一个障碍点的矩形中的最大子矩阵一定是极大子矩阵

定理2.一个极大矩阵的四边一定不能向外扩展，即每条边碰到障碍点或者边界

算法1

由于极大子矩形的4条边一定覆盖障碍点（或者边界） ——— 因此我们可以枚举每一个障碍点

1.把矩形的四个边界点也加入到障碍点的集合当中

s[++k].x = 0, s[k].y = 0;   //左上边界
s[++k].x = 0，s[k].y = m;   //右上边界
s[++k].x = n, s[k].y = 0;   //左下边界
s[++k].x = n, s[k].y = m;   //右下边界

2.对横坐标进行排序

3.枚举极大子矩阵的左边界，从左到右扫描每一个障碍点

4.不断修改可行的上下边界，从而得到所有以这个定点为左边界的极大子矩阵

一开始上下边界取的是牛场（矩形）的上下边界

更新上下边界

1.当前点的纵坐标比定点大 ，即当前点位于定点的上方，修改上边界为当前点的纵坐标

2.当前点位于定点的下方，则修改下边界为当前带你的纵坐标

3.当前点和定点位于同一位置，则结束扫描

for(int i=1;i<=k;i++)
{
    x1 = s[i].x;
    y1 = 0;    
    y2 = m;  
   for(int j=i+1;j<=k;j++）
    {
      x2 = s[j].x;
      if(s[i].y > s[j].y) y1 = max(y1,s[j].y);
      else y2 = min(y2,s[j].y);
      ans = max(ans,(x2-x1) * (y2-y1));
    }
}

5.枚举极大子矩阵的右边界，从右到左扫描每一个障碍点

由于从左到右扫描后可能会出现遗漏的情况，如极大子矩形的左边界是牛场的左边界，有边界覆盖一个障碍点

6.更新答案

ans = max(ans, (上边界 - 下边界 ）* 横坐标之差）

7.还有，极大子矩阵的左右边界与矩形的左右边界重合的情况；

我们将按照纵坐标进行排序，枚举相邻的两个纵坐标之间的极大子矩形

for(int i=1;i<=k-1;i++){
		ans = max(ans,n*(s[i+1].y-s[i].y));
	}

C++ Code

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

const int N = 3e5+10;

int n,m,k;
int ans;
struct Point {
	int x,y;
}s[N];

bool cmp1(Point a, Point b){
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y; 
}
bool cmp2(Point a, Point b){
	if(a.y != b.y) return a.y < b.y;
	return a.x < b.y;
}
int main(){
	cin>>n>>m>>k;
	
	for(int i=1;i<=k;i++){
		int x,y;
		cin>>x>>y;
		s[i] = {x,y};
	} 
	//加入矩形的四个边界点
	s[++k].x = 0, s[k].y = 0;
	s[++k].x = 0, s[k].y = m;
	s[++k].x = n, s[k].y = 0;
	s[++k].x = n, s[k].y = m;
	
	int x1,x2,y1,y2;
	
	sort(s+1,s+k+1,cmp1);
	
	for(int i=1;i<=k;i++){
		x1 = s[i].x; 
		y1 = 0, y2 = m;
		for(int j=i+1;j<=k;j++){
			x2 = s[j].x;
			ans = max(ans,(x2-x1)*(y2-y1));
			if(s[i].y > s[j].y) y1 = max(y1,s[j].y);
			else y2 = min(y2,s[j].y);
		}
	}
	
	for(int i=k;i>=1;i--){
		x1 = s[i].x;
		y1=0,y2=m;
		for(int j=i-1;j>=1;j--){
			x2 = s[j].x;
			ans = max(ans,(x1-x2)*(y2-y1));  //右边减去左边
			if(s[i].y > s[j].y) y1 = max(y1,s[j].y);
			else y2 = min(y2,s[j].y); 
		}
	} 
	
	sort(s+1,s+1+k,cmp2);
	
	for(int i=1;i<=k-1;i++){
		ans = max(ans,n*(s[i+1].y-s[i].y));
	}
	
	cout<<ans;
	return 0;
}