关键词: 矩形  极大子矩形  障碍点  悬线法 相关题目:奶牛浴场  月饼盒  巨大的牛棚

问题简述:在一个给定的矩形网格中有一些障碍点,要找出网格内部不包含任何障碍点,且边界与坐标轴平行的最大子矩形。 思想方法:极大化思想 例题:

奶牛浴场 (Winter Camp 2002)

题目描述

    由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛场中的一个固定的位置产奶,而奶牛显然不能在浴场中产奶,于是,John希望所建造的浴场不覆盖这些产奶点。这回,他又要求助于Clevow了。你还能帮助Clevow吗?     John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内,并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点,但是产奶点可以位于浴场的轮廓上。     Clevow当然希望浴场的面积尽可能大了,所以你的任务就是帮她计算浴场的最大面积。

输入输出格式

输入格式:     输入文件的第一行包含两个整数LLWW,分别表示牛场的长和宽。     文件的第二行包含一个整数nn,表示产奶点的数量。以下nn行每行包含两个整数xxyy,表示一个产奶点的坐标。所有产奶点都位于牛场内,即:0<=x<=L0<=x<=L0<=y<=W0<=y<=W输出格式:     输出文件仅一行,包含一个整数SS,表示浴场的最大面积。

数据规模

    0<=n<=50000<=n<=5000     1<=L,W<=300001<=L,W<=30000


解决方案

Step 1

定义:

  1. 有效子矩形:为内部不包含任何障碍点且边界与坐标轴平行的子矩形。如图所示,第一个是有效子矩形(尽管边界上有障碍点),第二个不是有效子矩形(因为内部含有障碍点)。 有效子矩形
  2. 极大有效子矩形:一个有效子矩形,如果不存在包含它且比它大的有效子矩形,就称这个有效子矩形为极大有效子矩形。(为了叙述方便,以下称为极大子矩形
  3. 最大有效子矩形:为所有有效子矩形中最大的一个(或多个)。(以下简称为最大子矩形

Step 2

极大化思想:

根据定义不难发现:在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形

Step 3

算法:

约定:为了叙述方便,设整个矩形的大小为n×m,其中障碍点个数为s。

    算法一

    根据这个思路可以发现,如果算法中有一次枚举的子矩形不是有效子矩形、或者不是极大子矩形,那么可以肯定这个算法做了“无用功”,这也就是需要优化的地方。很显然,可以保证每一次枚举的矩形都是极大子矩形。     操作如下:     首先,一个极大子矩形的四条边一定都不能向外扩展。更进一步地说,一个有效子矩形是极大子矩形的充要条件是这个子矩形的每条边要么覆盖了一个障碍点,要么与整个矩形的边界重合。             图1 接下去的第一想法:先在点阵中预处理四角上的四个点,因为四个点一定能确定一个极大子矩形,所以再在点阵中每次任取4个点,然后判断是否合法(内部是否有包含障碍点),这样得到的每个矩形一定是极大子矩形。说完,你肯定马上意识到这样的算法时间复杂度为 Θ(s5s^{5}) 显然太高。原因是每次枚举判断时产生了很多不合法的矩形。于是我们可以朝着一方面继续优化。 图2     正解:先从左到右扫描先枚举极大子矩形的左边界,然后从左到右依次扫描每一个障碍点(图3),并不断修改可行的上下边界(图4),从而枚举出所有以这个定点为左边界的极大子矩形。                    图3 图4     考虑如图2中的三个点,现在我们要确定所有以1号点为左边界的极大矩形。先将1号点右边的点按横坐标排序。然后按从左到右的顺序依次扫描1号点右边的点,同时记录下当前的可行的上下边界。可以发现,这样每次枚举的矩形都是极大子矩形。(想一想:是不是所有的极大子矩形都被枚举过了) 图5     注意:如果扫描到的点不在当前的上下边界内,那么就不需要对这个点进行处理。并且需要预处理四个角上的点。

    算算时间复杂度:Θ(s2s^{2}) 明显有很大感觉,还是很不错的。

    算法二

线

优势:不受障碍点个数影响。

    相比较上一种算法来讲从时间复杂度:Θ(s2s^{2}) 来讲,这种方法收到障碍点个数的影响。当在点很稠密的图中发挥不了绝大的优势。而悬线法恰解决了这一问题。     我们需要换一种思路去思考......     定义:     1. 有效竖线:除了两个端点外,不覆盖任何障碍点的竖直线段。     2. 悬线:上端点覆盖了一个障碍点或达到整个矩形上端的有效竖线。     如图所示的三个有效竖线都是悬线。         2     对于任何一个极大子矩形,它的上边界上要么有一个障碍点,要么和整个矩形的上边界重合。那么如果把一个极大子矩形按x坐标不同切割成多个(实际上是无数个)与y轴垂直的线段(想象一下),则其中一定存在一条悬线(可依照图4)。而且一条悬线通过尽可能地向左右移动恰好能得到一个子矩形(未必是极大子矩形,但只可能扩展)。那么如果将一个悬线向左右两个方向尽可能移动所得到的有效子矩形称为这个悬线所对应的子矩形,那么所有悬线所对应的有效子矩形的集合一定包含了所有极大子矩形的集合。(#废话     当然了,首先是要保证最大子矩阵,即移动到障碍点边界为止。     可以发现,通过枚举所有的悬线,就可以枚举出所有的极大子矩形。由于每个悬线都与它底部的那个点一一对应,所以悬线的个数= (以矩形中除了顶部的点以外的每个点为底部,都可以得到一个悬线,且没有遗漏)。如果能做到对每个悬线的操作时间都为Θ(11),那么整个算法的复杂度就是Θ(NMNM)。这样,我们看到了解决问题的希望。     那么问题来了,怎样在Θ(1)的时间内完成对每个悬线的操作。我们知道,每个极大子矩形都可以通过一个悬线左右平移得到。所以,对于每个确定了底部的悬线,我们需要知道有关于它的三个量:顶部、左右最多能移动到的位置。对于底部为(i,j)的悬线,设它的高为hight[i,j],左右最多能移动到的位置为left[i,j],right[i,j]。为了充分利用以前得到的信息,我们将这三个函数用递推的形式给出。 先给图吧:         对于以点(i,j)为底部的悬线: 如果点(i-1,j)为障碍点,那么,显然以(i,j)为底的悬线高度为1,而且左右均可以移动到整个矩形的左右边界,即

height[i,j]=1     left[i,j]=0     right[i,j]=m     (初始化)

    如果点(i-1,j)不是障碍点,那么以(i,j)为底的悬线就=以(i-1,j)为底的悬线+点(i,j)到点(i-1,j)的线段。因此,height[i,j]=height[i-1,j]+1。比较麻烦的是左右边界,先考虑left[i,j]。如下图所示,(i,j)对应的悬线左右能移动的位置要在(i-1,j)的基础上变化。即     height[i,j]=height[i-1,j]+1     left[i,j]=max( left[i-1,j] , (i-1,j)左边第一个障碍点位置 )     right[i,j]=max( right[i-1,j] , (i-1,j)右边第一个障碍点位置 )     示意图:             这样做充分利用了以前得到的信息,使每个悬线的处理时间复杂度为O(1)。对于以点(i,j)为底的悬线对应的子矩形,它的面积为( right[i,j]-left[i,j] )*height[i,j]。     这样最后问题的解就是:

    Result=max(right[i,j]-left[i,j])*height[i,j] (l<=i<nl<=i<nl<=j<=ml<=j<=m)

    Perfect!

    总结:以上说了两种具有一定通用性的处理算法,时间复杂度分别为Θ(s2s^{2})和Θ(NMNM)。两种算法分别适用于不同的情况。从时间复杂度上来看,第一种算法对于障碍点稀疏的情况比较有效,第二种算法则与障碍点个数的多少没有直接的关系(当然,障碍点较少时可以通过对障碍点坐标的离散化来减小处理矩形的面积,不过这样比较麻烦,不如第一种算法好),适用于障碍点密集的情况。


AC代码:

算法一

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define drep(i,a,b) for(re i=(a);i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int N=5e3+7;
struct Cow{
int x,y;
inline bool operator < (const Cow &rhs) const{
if(x!=rhs.x) return x<rhs.x;
return y<rhs.y;
}
}a[N];

int L,W,n;

inline bool cmp(Cow a,Cow b){
return a.y<b.y;
}

inline void read(int &x){
x=0;
int f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}

int main(){
read(L),read(W),read(n);
rep(i,1,n) read(a[i].x),read(a[i].y);
a[++n].x=0;a[n].y=0;
a[++n].x=L;a[n].y=0;
a[++n].x=0;a[n].y=W;
a[++n].x=L;a[n].y=W;
//预处理四个角上的点
std::sort(a+1,a+n+1);
int res=0;
rep(i,1,n){
//确定一个障碍点
int h=W,l=0,v=L-a[i].x;
rep(j,i+1,n)//确定最右障碍点
if(a[j].y<=h&&a[j].y>=l){//确保该点在内部(否则不必讨论)
if(v*(h-l)<=res) break;//往右扫理想最大值比当前值小(pass)
res=max(res,(a[j].x-a[i].x)*(h-l));
if(a[j].y==a[i].y) break;//面积为0且成为后面的障碍点(pass)
if(a[j].y>a[i].y) h=min(h,a[j].y);
else l=max(l,a[j].y);
//每次操作后调整区间范围
}
h=W,l=0,v=a[i].x;
drep(j,i-1,1)
if(a[j].y<=h&&a[j].y>=l){
if(v*(h-l)<=res) break;
res=max(res,(a[i].x-a[j].x)*(h-l));
if(a[i].y==a[j].y) break;
if(a[j].y>a[i].y) h=min(h,a[j].y);
else l=max(l,a[j].y);
}
}
std::sort(a+1,a+n+1,cmp);
rep(i,1,n-1) res=max(res,(a[i+1].y-a[i].y)*L);
//枚举以左右两边作为矩形边界的情况
printf("%d\n",res);
return 0;
}

参考文献:[国家集训队2003论文集] 王知昆