Day \(4!\)。
首先容易找到周长为 \(2(w+1)\) 和 \(2(h+1)\) 的矩形，所以答案下界是 \(2(\max(w,h)+1)\)。
考虑按照整个矩形中心坐标，将矩形分成 \(4\) 个子矩形，观察到若有矩形完全包含于其中一个子矩形，则其周长必不超过 \(2\max(w,h)\)，必然不是最优解。所以最优解一定被直线 \(2x=w\) 或者 \(2y=h\) 穿过。
先考虑被直线 \(2x=w\) 穿过的情况，后者可以通过将 \((x,y)\) 两维坐标交换转换为前者。
设将 \(x\) 坐标离散化后第 \(i\) 个坐标为 \(t_i\)，第 \(i\) 个点坐标为 \((x_i,y_i)\)。为了方便，加入 \((0,0)\) 点和 \((w,h)\) 点，先计算 \(t_i\) 到 \(t_{i+1}\) 形成周长 \(2(t_{i+1}-t_i+h)\) 的矩形，然后剩下的矩形中必定至少跨过三个坐标 \(t_l,t_j,t_r\)。
考虑扫描线，从左到右枚举答案矩形的右边界为 \(t_r\)，设左边界为 \(t_l\)，那么只有 \(l<j<r\) 的点对矩形有限制。令 \(u_i=\min\limits_{x_j=i,2y_j>w}y_j\)，\(d_i=\max\limits_{x_j=i,2y_j\le w}y_j\)：
\[\begin{aligned}\text{ans}&=t_r+\max\limits_{1\le l\le r-2}\left(-t_l+\min\limits_{l<i<r}u_i-\max\limits_{l<i<r}d_i\right)\\&=t_r+\max\limits_{2\le l<r}\left(-t_{l-1}+\min\limits_{l\le i<r}u_i-\max\limits_{l\le i<r}d_i\right)\end{aligned}
\]
然后直接经典线段树 + 单调栈维护即可。复杂度 \(O(n\log n)\)。
// Problem: F - Snuke's Coloring 2
// Contest: AtCoder - AtCoder Regular Contest 063
// URL: https://atcoder.jp/contests/arc063/tasks/arc063_d
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Med;
const int N = 1e6 + 100;
int ans, w, h, n, len, tp[2];
int tx[N], up[N], dn[N], st[N][2];
pi t[N], a[N];
vector<int> g[N];
struct SEG {
int mx[N << 2], ad[N << 2];
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
void pup(int x) { mx[x] = max(mx[ls], mx[rs]); }
void ptg(int x, int c) { mx[x] += c, ad[x] += c; }
void pdn(int x) { ad[x] && (ptg(ls, ad[x]), ptg(rs, ad[x]), ad[x] = 0); }
void upd(int l, int r, int p, int c, int x) {
if (l == r) return mx[x] = c, ad[x] = 0, void();
pdn(x);
if (p <= mid) upd(l, mid, p, c, ls);
else upd(mid + 1, r, p, c, rs);
pup(x);
}
void add(int l, int r, int s, int t, int c, int x) {
if (s <= l && r <= t) return ptg(x, c);
pdn(x);
if (s <= mid) add(l, mid, s, t, c, ls);
if (t > mid) add(mid + 1, r, s, t, c, rs);
pup(x);
}
int qry(int l, int r, int s, int t, int x) {
if (s <= l && r <= t) return mx[x];
pdn(x);
if (s > mid) return qry(mid + 1, r, s, t, rs);
else if (t <= mid) return qry(l, mid, s, t, ls);
return max(qry(l, mid, s, t, ls), qry(mid + 1, r, s, t, rs));
}
};
void calc() {
len = tp[0] = tp[1] = 0;
for (int i = 1; i <= n; i++) tx[++len] = t[i].fi;
sort(tx + 1, tx + len + 1), len = unique(tx + 1, tx + len + 1) - tx - 1;
for (int i = 1; i <= len; i++) g[i].clear();
for (int i = 1; i <= n; i++) {
t[i].fi = lower_bound(tx + 1, tx + len + 1, t[i].fi) - tx;
g[t[i].fi].pb(t[i].se);
}
for (int i = 2; i <= len; i++)
ans = max(ans, h + (tx[i] - tx[i - 1]));
for (int i = 1; i <= len; i++) {
up[i] = h, dn[i] = 0;
for (int j : g[i]) {
if (j > w / 2) up[i] = min(up[i], j);
else dn[i] = max(dn[i], j);
}
}
SEG T;
for (int i = 2; i <= len; i++) {
while (tp[0] && up[st[tp[0]][0]] > up[i - 1])
T.add(1, len, st[tp[0] - 1][0] + 1, st[tp[0]][0], up[i - 1] - up[st[tp[0]][0]], 1), tp[0]--;
while (tp[1] && dn[st[tp[1]][1]] < dn[i - 1])
T.add(1, len, st[tp[1] - 1][1] + 1, st[tp[1]][1], dn[st[tp[1]][1]] - dn[i - 1], 1), tp[1]--;
st[++tp[0]][0] = st[++tp[1]][1] = i - 1;
if (i <= 2) continue;
T.upd(1, len, i - 1, - tx[i - 2] + up[i - 1] - dn[i - 1], 1);
ans = max(ans, T.qry(1, len, 2, i - 1, 1) + tx[i]);
}
}
void solve() {
cin >> w >> h >> n;
for (int i = 1, x, y; i <= n; i++)
cin >> x >> y, t[i] = a[i] = mp(x, y);
n += 2, t[n - 1] = a[n - 1] = mp(0, 0), t[n] = a[n] = mp(w, h);
sort(t + 1, t + n + 1), calc(), swap(w, h);
for (int i = 1; i <= n; i++) t[i] = mp(a[i].se, a[i].fi);
sort(t + 1, t + n + 1), calc();
cout << ans * 2 << '\n';
}
bool Mbe;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Med - &Mbe) / 1048576.0 << " MB\n";
#ifdef FILE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}