题解 P1578 【奶牛浴场】

· · 题解

其它的题解都没怎么看懂...于是就自己 yy 了一个做法

解析

思考一个极大矩形会满足什么条件

我们可以证明它的每条边上（不含顶点）一定有一个障碍点或者这条边和边界重合

因为如果一条边不满足上述条件，我们一定可以移动这条边并获得更大的矩形

并且我们还发现，极大矩形的边上至少有一个障碍点，除非整张图没有障碍点（这个要特判）

于是我们就可以枚举障碍点作为极大矩形边上的点，然后在按坐标排序（具体看枚举的边和哪个坐标轴平行），一点点限制矩形边界，求出当前限制下矩形的最大可能面积再取个 \text{max} 即可。

 

具体的实现方式可能各有差异，这里解释一种可能的实现

（下面的 y 坐标即题目输入的 y（W，宽），x 坐标同）

我们枚举极大矩形的左右边（和 y 轴平行，为什么不枚举上下边见下文）。每次枚举一个点 A 作为极大矩形左/右边时，按 x 坐标排序并从近到远加入 x 坐标大于/小于该点的障碍点；每加入一个点，如果其 y 坐标小于当前点，就上移矩形下边，如果大于就下移矩形上边（为了让 A 仍在矩形边上），如果等于就停止枚举；此时将已枚举障碍点之间最大的 x 坐标差作为矩形底长，上下边 y 坐标差作为高，就是一种可能的答案。

因为这里实现的特性，我直接将边界矩形的四个顶点作为障碍点直接带入算法，但不将这四个点枚举作为初始矩形左/右边上的点（具体见代码），这样就可以不特判极大矩形左右边在边界的情况。根据具体实现可能需要其它的方式处理这个问题

另外，我们最后还要枚举遗漏的极大矩形左右边都在边界上的特殊情况。可以想到，设此时极大矩形上边的 y 坐标 a，下边的 y 坐标 b，肯定没有 y 坐标在 (a, b) 这个区间内的障碍点；否则矩形左右边就不可能都在边界上。这个将障碍点按 y 坐标排序后 O(n) 枚举 y 坐标相邻的障碍点作为高即可

CODE

对于 x 坐标相同的障碍点需要一些特判，具体见代码以及 这个 帖子

#include <cstdio>
#include <algorithm>
using std::max;
using std::min;
using std::sort;

const int MAXN =5000+50;

inline int read(){
    int x =0; char c =getchar();
    while(c < '0' || c > '9') c =getchar();
    while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (48^c), c =getchar();
    return x;
}

int L, W;/*长 宽 ( 列 行 )*/
struct milk{
    int x, y, typ;
}block[MAXN];

bool cmp1(milk A, milk B){
    return A.x < B.x;
}

bool cmp2(milk A, milk B){
    return A.x > B.x;
}

bool cmp3(milk A, milk B){
    return A.y < B.y;
}

inline int abs(int x){ return (x < 0) ? -x : x; }

int main(){
    L =read(), W =read();
    int n =read();
    if(n == 0)
        return printf("%d", L*W) && 0;
    for(int i =0; i < n; ++i)
        block[i].x =read(), block[i].y =read();
    block[n].x =0, block[n].y =0, block[n].typ =1;
    block[n+1].x =L, block[n+1].y =0, block[n+1].typ =1;
    block[n+2].x =0, block[n+2].y =W, block[n+2].typ =1;
    block[n+3].x =L, block[n+3].y =W, block[n+3].typ =1;

    int ANS =0;
    /*使得当前障碍点在矩形边界上*/
    for(int k =0; k < 2; ++k){
        if(k == 0)
            sort(block, block+n+4, cmp1);
        else
            sort(block, block+n+4, cmp2);
        for(int i =0; i < n+4; ++i){
            if(block[i].typ == 1)
                continue;
            int up =0, down =W, l =0;
            for(int j =i+1; j < n+4; ++j){
                if(block[j].x == block[i].x)/*注意这里的特判*/
                    continue;
                l =abs(block[j].x-block[i].x);
                ANS =max(ANS, (down-up)*l);
                if(block[j].y == block[i].y)
                    break;
                if(block[j].y < block[i].y)
                    up =max(up, block[j].y);
                else
                    down =min(down, block[j].y);
            }
        }
    }
    sort(block, block+n+4, cmp3);
    for(int i =0; i < n+4-1; ++i)
        ANS =max(ANS, (block[i+1].y-block[i].y)*L);
    printf("%d", ANS);
}