好题一道。
一个很 trivial 的发现是答案等价于求一个周长最大的矩形,满足这个矩形内部(不含边界)没有其他点。
首先注意到一个性质:答案肯定不小于 \(2\max(H,W)+2\),这是因为我们肯定可以框出一个 \(1\times\max(H,W)\) 的矩形,其内部肯定不会含其他点。考虑通过这个简单的性质我们可以得到什么。我们考虑将矩形从 \(x=\dfrac{W}{2},y=\dfrac{H}{2}\) 处劈成四个部分,那么可以发现,对于完全包含在四个部分之一的矩形,其周长最大不会超过 \(2(\dfrac{W}{2}+\dfrac{H}{2})=W+H<2\max(H,W)+2\),也就是说,在最优决策方案中,\(x\) 轴和 \(y\) 轴中至少有一个方向是跨过中线的,这里我们不妨假设 \(y\) 轴跨过中线,\(x\) 轴跨过中线的情况用类似方法求一下即可。
我们考虑将所有点按 \(x\) 坐标从小到大排序然后枚举最终矩形的左右端点,或者说,横坐标等于左边界的点 \(i\) 和横坐标等于右边界的点 \(j\)(由于我们已经将所有点按横坐标从小到大排序,因此必然有 \(i<j\)),那么我们考虑纵坐标的范围,如果 \(j=i+1\) 那么显然纵坐标的范围可以是 \([0,H]\),该矩形对答案的贡献就是其周长 \(2(H+x_j-x_i)\),否则,我们考虑 \([i+1,j-1]\) 中的一个点 \(k\),如果 \(2y_k\le H\),那么由于我们强制要求其跨过中线,该矩形的下边界必须高于 \(y_k\),否则 \(2y_k>H\),该矩形的下边界也就应低于 \(y_k\)。这样我们可以得到矩形的上下边界,然后令答案对其取 \(\max\) 即可。
直接枚举是平方的,考虑优化。我们记 \(l_i,r_i\) 表示点 \(i\) 对矩形纵坐标范围的限制,具体来说如果 \(2y_i\le H\) 那么 \(l_i=y_i,r_i=H\),否则 \(l_i=0,r_i=y_i\),那么一组 \(i,j(i\le j-2)\) 对答案的贡献即为 \(2(x_j-x_i+(\max\limits_{k=i+1}^{j-1}r_k)-(\min\limits_{k=i+1}^{j-1}l_k))\),对 \(l,r\) 分别建一个单调栈处理掉即可。时间复杂度 \(n\log n\)。
using namespace fastio;
const int MAXN = 1e6;
const ll INFll = 0x3f3f3f3f3f3f3f3fll;
int W, H, n;
struct point {
int x, y;
friend bool operator < (point lhs, point rhs) {
return lhs.x < rhs.x;
}
} p[MAXN + 5];
struct node {int l, r; ll mx, lz;} s[MAXN * 4 + 5];
void pushup(int k) {s[k].mx = max(s[k << 1].mx, s[k << 1 | 1].mx);}
void build(int k, int l, int r) {
s[k].l = l; s[k].r = r; s[k].mx = s[k].lz = 0; if (l == r) return;
int mid = l + r >> 1; build(k << 1, l, mid); build(k << 1 | 1, mid + 1, r);
}
void tag(int k, ll v) {s[k].mx += v; s[k].lz += v;}
void pushdown(int k) {if (s[k].lz) tag(k << 1, s[k].lz), tag(k << 1 | 1, s[k].lz), s[k].lz = 0;}
void modify(int k, int l, int r, int v) {
if (l > r) return;
if (l <= s[k].l && s[k].r <= r) return tag(k, v), void();
pushdown(k); int mid = s[k].l + s[k].r >> 1;
if (r <= mid) modify(k << 1, l, r, v);
else if (l > mid) modify(k << 1 | 1, l, r, v);
else modify(k << 1, l, mid, v), modify(k << 1 | 1, mid + 1, r, v);
pushup(k);
}
ll query(int k, int l, int r) {
if (l > r) return -INFll;
if (l <= s[k].l && s[k].r <= r) return s[k].mx;
pushdown(k); int mid = s[k].l + s[k].r >> 1;
if (r <= mid) return query(k << 1, l, r);
else if (l > mid) return query(k << 1 | 1, l, r);
else return max(query(k << 1, l, mid), query(k << 1 | 1, mid + 1, r));
}
stack<pii> up, dw;
void insup(int x, int p) {
while (up.size() > 1 && up.top().fi > p) {
pii pp = up.top(); up.pop();
modify(1, up.top().se, pp.se - 1, -pp.fi);
}
modify(1, up.top().se, x - 1, p);
up.push(mp(p, x));
}
void insdw(int x, int p) {
while (dw.size() > 1 && dw.top().fi < p) {
pii pp = dw.top(); dw.pop();
modify(1, dw.top().se, pp.se - 1, pp.fi);
}
modify(1, dw.top().se, x - 1, -p);
dw.push(mp(p, x));
}
ll calc() {
sort(p + 1, p + n + 1);
build(1, 0, n + 1); ll mx = 0;
up.push(mp(0, 0)); dw.push(mp(0, 0));
for (int i = 1; i <= n + 1; i++) {
if (p[i - 1].y < H / 2) {
insup(i - 1, H);
insdw(i - 1, p[i - 1].y);
} else {
insup(i - 1, p[i - 1].y);
insdw(i - 1, 0);
}
modify(1, i - 1, i - 1, -p[i - 1].x);
chkmax(mx, query(1, 0, i - 2) + p[i].x);
chkmax(mx, p[i].x - p[i - 1].x + H);
}
while (!up.empty()) up.pop();
while (!dw.empty()) dw.pop();
return mx;
}
int main() {
// freopen("4-etzoob-244.in", "r", stdin);
// freopen("4-etzoob-244.out", "w", stdout);
read(n); read(W); read(H);
for (int i = 1; i <= n; i++) read(p[i].x), read(p[i].y);
p[n + 1] = {W, H}; ll res = calc();
for (int i = 1; i <= n + 1; i++) swap(p[i].x, p[i].y);
swap(W, H); chkmax(res, calc());
printf("%lld\n", res << 1);
return 0;
}