因为这题考虑可以观察一个性质,答案的下界为 \(2×(max(w,h)+1)\), 因为你至少可以空出一行或一列,因此这个矩形一定会经过 \(x=\frac{w}{2}\) 或 \(y=\frac{h}{2}\) . 先考虑经过 \(\frac{w}{2}\) 的情况 , 另一种情况是一样的.
先将坐标离散化.枚举矩形的上边界 \(yR\) ,对于每一个下边界 \(yL\) , 我们可以计算出矩形的最优左边界 \(xL=min\{Xi|Yi\in[yL,yR],Xi>\frac{w}{2}\}\) , 以 及 右 边 界 \(xR=max\{Xi|Yi\in[yL,yR],Xi≤\frac{w}{2}\}\) ,
此时可以找到一个周长为 \(2×(xR−xL+yR−yL)\) 的矩形.
直接做是 \(O(n^2)\) 的,但该算法可以用线段树优化,在将上边界往上移的过程中动态维护每
个位置的 xL,xR,并维护全局最小值,不难发现只需要左右各开一个单调栈,在更新单调栈
时在线段树树上进行区间加减即可. O(nlogn) .
这其实就是一个计算极大subrectangle的过程, 因为知道中间边界, 基本原理来自于暴力, 就是简单的枚举长度, 更新宽度. 其实这题也很套路, 发现这题的边界是不断移动的, 在移动的时候会产生一部分的重复信息, 所以考虑采用数据结构维护, 分析一下颓余状态, 发现可以单调栈优化.
Code
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
char ch = getchar();
int x = 0, flag = 1;
for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x * flag;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) write(x / 10);
putchar(x % 10 + 48);
}const int Maxn = 3e5 + 9;
struct Point {
int x, y;
int operator < (const Point &a) const {
return x < a.x;
}
}s[Maxn];
int n, ans, h, w;void init() {
w = read(), h = read(); n = read();
rep (i, 1, n) s[i].x = read(), s[i].y = read();
s[++n] = (Point){0, 0};
s[++n] = (Point){w, h};
}pair<int, int> stkA[Maxn], stkB[Maxn];
int topa, topb;struct SGMTtree {
int tree[Maxn << 2], add[Maxn << 2];
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ls rt << 1, l, mid
#define rs rt << 1 | 1, mid + 1, rvoid clear() {
clar(tree, 0), clar(add, 0);
}
void pushup(int rt) {
tree[rt] = max(tree[lc(rt)], tree[rc(rt)]);
}
void pushdown(int rt) {
if (add[rt]) {
add[lc(rt)] += add[rt]; add[rc(rt)] += add[rt];
tree[lc(rt)] += add[rt]; tree[rc(rt)] += add[rt];
add[rt] = 0;
}
}
void modify(int rt, int l, int r, int p, int q, int v) {
if (p <= l && r <= q) {
add[rt] += v; tree[rt] += v;
return ;
}int mid = (l + r) >> 1; pushdown(rt);
if (q <= mid) modify(ls, p, q, v);
else if (p >= mid + 1) modify(rs, p, q, v);
else modify(ls, p, q, v), modify(rs, p, q, v);
pushup(rt);
}
#undef lc
#undef rc
#undef ls
#undef rs
}st;void ZhaoQingFei() {
sort(s + 1, s + n + 1);st.clear(); topa = topb = 0;
rep (i, 1, n) {
int Nxt = i - 1;
if (s[i].y <= h / 2) {
while (topa && stkA[topa].second <= s[i].y) {
st.modify(1, 1, n, stkA[topa].first, Nxt, stkA[topa].second - s[i].y);
Nxt = stkA[topa].first - 1; --topa;
}
if (Nxt != i - 1) stkA[++topa] = make_pair(Nxt + 1, s[i].y);
} else {
while (topb && stkB[topb].second >= s[i].y) {
st.modify(1, 1, n, stkB[topb].first, Nxt, s[i].y - stkB[topb].second);
Nxt = stkB[topb].first - 1; --topb;
}
if (Nxt != i - 1) stkB[++topb] = make_pair(Nxt + 1, s[i].y);
}
stkA[++topa] = make_pair(i, 0);
stkB[++topb] = make_pair(i, h);st.modify(1, 1, n, i, i, h - s[i].x);
ans = max(ans, s[i + 1].x + st.tree[1]);
}
}void solve() {
ZhaoQingFei();rep (i, 1, n) swap(s[i].x, s[i].y);
swap(h, w);ZhaoQingFei();
cout << ans * 2 << endl;
}int main() {
//freopen("ARC047B.in", "r", stdin);
//freopen("ARC047B.out", "w", stdout);init();
solve();#ifdef Qrsikno
debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
return 0;
}
更新防死
