##题解##洛谷P1578##最大子矩形 扫描线法

[传送门](P1578 [WC2002] 奶牛浴场 - 洛谷)

题意概述

在矩形里放置若干障碍点，求各边平行于原矩形的最大子矩形（子矩形不包含障碍点）

分析

1. 最大子矩形容易想到悬链线方法，然而时间复杂度O(LW) L，W均为3*1e4大小，会超时。

2. 我们注意到障碍点n的个数只有5000，于是我们通过枚举障碍点的方法枚举极大子矩形，再找出最大子矩形。

参考wzk《浅谈用极大化思想解决最大子矩形问题》

算法实现

将整个矩形四个顶点加入障碍点集合

双指针枚举横坐标，得到双障碍点组

以双障碍点组为左右边界，确定上下边界，找到极大子矩形

流程如图

代码实现

#include<bits/stdc++.h>
using namespace std;
int read()
{int sum = 0, f = 1;char c = getchar();while (c< '0' or c>'9'){if (c == '-')f = -1;c = getchar();}while (c >= '0' and c <= '9'){sum = (sum << 1) + (sum << 3) + c - '0';c = getchar();}return sum * f;
}struct S
{int x, y;
} s[5010];bool cmp1(S a, S b)
{if (a.x != b.x) return a.x < b.x;else return a.y < b.y;
}bool cmp2(S a, S b)
{if (a.y != b.y) return a.y < b.y;else return a.x < b.x;
}int l, w, n, ans;int main()
{l = read(), w = read(), n = read();for (int i = 1; i <= n; i++)s[i].x = read(), s[i].y = read();s[++ n].x = 0, s[n].y = 0; //将四个顶点设为障碍点s[++ n].x = 0, s[n].y = w;s[++ n].x = l, s[n].y = 0;s[++ n].x = l, s[n].y = w;int x1, x2, y1, y2;
//从左往右sort(s + 1, s + 1 + n, cmp1);for (int i = 1; i <= n; i++){x1 = s[i].x, y1 = 0, y2 = w;for (int j = i + 1; j <= n; j++){x2 = s[j].x;ans = max(ans, (x2 - x1) * (y2 - y1));if (s[j].y < s[i].y) y1 = max(y1, s[j].y);else y2 = min(y2, s[j].y);}}
//从右往左for (int i = n; i >= 1; i--){x1 = s[i].x, y1 = 0, y2 = w;for (int j = i - 1; j >= 1; j--){x2 = s[j].x;ans = max(ans, (x2 - x1) * (y2 - y1));if (s[j].y < s[i].y) y1 = max(y1, s[j].y);else y2 = min(y2, s[j].y);}}
//从下往上，以整个矩形边界为极大子矩形的边sort(s + 1, s + n + 1, cmp2);for (int i = 1; i <= n - 1; i++)ans = max(ans, l * (s[i + 1].y) - s[i].y);printf("%d", ans);
}

Trick/错误总结

1. 快读

2. 最大子矩形扫描线法：O(S)

3. 最大子矩形悬线法：O（MN）