题解 P1578 【奶牛浴场】

· · 题解

在此说句不太好听的话，其实楼下两位的代码都是错误的，只是没有数据把其检测出来。

如（换行可能被删，请根据题意自行脑补）：10 10

3 3 0 8 2 3 9 正确答案应该是72，而他们的都是56.

其实还有：10 10

2 8 1 3 9 正确答案应该是80，而他们都是72.

这个题目很出名，可以在百度搜索王知昆国家队dalao的论文，其中说的非常详细，但是可惜的是在他本人的代码中也有两个bug，我上面的两组数据他的代码也出现的错误。可能是由于本题数据较水，所以很多有bug的代码水过去了。

我来简单的说一下：

先枚举极大子矩形的左边界，然后从左到右依次扫描每一个障碍点，并不断修改可行的上下边界，从而枚举出所有以这个定点为左边界的极大子矩形。考虑如图2中的三个点，现在我们要确定所有以1号点为左边界的极大矩形。先将1号点右边的点按横坐标排序。然后按从左到右的顺序依次扫描1号点右边的点，同时记录下当前的可行的上下边界。

开始时令当前的上下边界分别为整个矩形的上下边界。然后开始扫描。第一次遇到2号点，以2号点作为右边界，结合当前的上下边界，就得到一个极大子矩形（如图3）。

同时，由于所求矩形不能包含2号点，且2号点在1号点的下方，所以需要修改当前的下边界，即以2号点的纵坐标作为新的下边界。第二次遇到3号点，这时以3号点的横坐标作为右边界又可以得到一个满足性质1的矩形（如图4）。

类似的，需要相应地修改上边界。以此类推，如果这个点是在当前点（确定左边界的点）上方，则修改上边界；如果在下方，则修改下边界；如果处在同一行，则可中止搜索（因为后面的矩形面积都是0了）。由于已经在障碍点集合中增加了整个矩形右上角和右下角的两个点，所以不会遗漏右边界与整个矩形的右边重合的极大子矩形（如图5）。

需要注意的是，如果扫描到的点不在当前的上下边界内，那么就不需要对这个点进行处理。

这样做是否将所有的极大子矩形都枚举过了呢？

可以发现，这样做只考虑到了左边界覆盖一个点的矩形，因此我们还需要枚举左边界与整个矩形的左边界重合的情况。这还可以分为两类情况。一种是左边界与整个举行的左边界重合，而右边界覆盖了一个障碍点的情况，对于这种情况，可以用类似的方法从右到左扫描每一个点作为右边界的情况。这就是上面第一个数据楼下二位错在哪里。

另一种是左右边界均与整个矩形的左右边界重合的情况，对于这类情况我们可以在预处理中完成：先将所有点按纵坐标排序，然后可以得到以相邻两个点的纵坐标为上下边界，左右边界与整个矩形的左右边界重合的矩形，显然这样的矩形也是极大子矩形，因此也需要被枚举到。这就是上面第二个数据楼下两位错在哪里。

对于开始预处理，需要人为添加0,0;0，l；w，0；l，w四个点，这时王知昆dalao错的第一个地方。

对于他其中的一个剪枝优化显然是不小心打错了。具体会在代码中说。

参考代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#define re register
#define REP(i,a,b) for (re int i=(a);i<=(b);i++)
#define DREP(i,a,b) for (re int i=(a);i>=(b);i--)
using namespace std;
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 int read(){
    re int x=0,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();}
    return x*f;
}
int main(){
    L=read(),W=read(),n=read();
    REP(i,1,n)a[i].x=read(),a[i].y=read();
    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;
    sort(a+1,a+n+1);
    int res=0;
    REP(i,1,n){
        re 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;
            res=max(res,(a[j].x-a[i].x)*(h-l));
            if (a[j].y==a[i].y)break;
            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;//王知昆dalao在此处仍将v设为l-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);
        }
    }
    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",res);
    return 0;
}