显然极大子矩形的任意边界要么上面有障碍点，要么贴着整个矩形的边界。
枚举上边界，这样我们就只需要考虑上边界下面的那些点了，正反预处理出 \(x\) 轴严格单调递增的单调栈。再枚举下边界上的障碍点，根据向左向右能到的最远位置计算面积。
具体实现时可以添加 \((0,0)\) 这个点，解决上边界贴着整个矩形的上边界的问题。对于下边界贴着整个矩形的下边界的问题，直接暴力枚举这若干段下边界即可。
P1578 奶牛浴场
发布时间 2023-07-01 21:22:34作者: 御坂夏铃
显然极大子矩形的任意边界要么上面有障碍点，要么贴着整个矩形的边界。
枚举上边界，这样我们就只需要考虑上边界下面的那些点了，正反预处理出 \(x\) 轴严格单调递增的单调栈。再枚举下边界上的障碍点，根据向左向右能到的最远位置计算面积。
具体实现时可以添加 \((0,0)\) 这个点，解决上边界贴着整个矩形的上边界的问题。对于下边界贴着整个矩形的下边界的问题，直接暴力枚举这若干段下边界即可。