传送门

问题可以转化成选一个周长最长的矩形使其内部不包含任何点。

首先答案有一个性质就是一定穿过横竖两条中线之一。因为如果两条都不穿过,即缩整个矩形的四分之一里,是没有选$\max(H,W)$再加一条长度为1的边组成的矩形优的。我们先只考虑穿过竖中线的情况,横中线的情况可以把所有东西旋转九十度后转化成竖中线。

在穿过竖中线的同时,我们再对纵坐标分治,每次分治到纵坐标在$[y_l,y_r]$的区间时,我们选最中间的点的纵坐标$y_m$,先递归算出纵坐标在$[y_l,y_m]$或$[y_m,y_r]$中的答案,剩下的就只用考虑同时穿过$x=x_m=W/2$和$y=y_m$两条直线的矩形了。

我们从右往左枚举矩形左边那条边的横坐标$x_l$,并对每个$x_l$处理出所有横坐标在$[x_l,x_m]$且纵坐标在$[y_l,y_m]$中的点的最大的纵坐标$y_1$,以及所有横坐标在$[x_l,x_m]$且纵坐标在$[y_m,y_r]$中的点的最小的纵坐标$y_2$。最终的矩形底边一定在$y_1$上方,顶边一定在$y_2$下方。同样,我们也枚举右边的横坐标$x_r$,并处理出意义相同的$y_1$和$y_2$。这样,两个$x_l$和$x_r$围出来的矩形的底边就是两个$y_1$的较大值,顶边就是$y_2$的较小值。考虑对每个$x_l$找出最优的$x_r$,我们发现可以把右边的所有$x_r$分成三段,第一段的$[y_1,y_2]$完全包含$x_l$的$[y_1,y_2]$;第二段不完全包含,但不被$x_l$的$[y_1,y_2]$包含;第三段则完全被$x_l$的$[y_1,y_2]$包含。第一段的答案很好处理,直接取最靠右的$x_r$就行了,后两段也能通过分别维护单调队列来进行统计(其中第二段还要分为上下两种情况)。这样,在把横坐标排好序之后,我们可以线性地统计出同时穿过$x_m$和$y_m$的答案。排序也可以用归并排序来做到线性,这样总复杂度就是$O(n\log n)$了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#define MAXN 300010
#define y1 zjtsb_y1
using namespace std;

int w,h,n,w0;
pair<int,int> a[MAXN];
deque<int> S1,S2,S3;

bool cmp2(pair<int,int> x,pair<int,int> y){
    return x.second<y.second;
}

int gao(int l,int r,int y0,int y1){
    if(l==r) return max(max(w+a[l].second-y0,w+y1-a[l].second),max(y1-y0+a[l].first,y1-y0+w-a[l].first));
    int mid=(l+r)>>1;
    int ymid=a[mid].second;
    int res1=gao(l,mid,y0,a[mid].second);
    int res2=gao(mid+1,r,a[mid+1].second,y1);
    sort(a+l,a+r+1);
    int mid2=l-1;
    while(mid2<r && a[mid2+1].first<=w0) mid2++;
    static int s1[MAXN][3],s2[MAXN][3];
    int ls1=0,ls2=0;
    int t0=y0,t1=y1;
    for(int i=mid2;i>=l;i--){
        s1[++ls1][0]=t0;
        s1[ls1][1]=t1;
        s1[ls1][2]=a[i].first;
        if(a[i].second<=ymid && a[i].second>t0) t0=a[i].second;
        if(a[i].second>ymid && a[i].second<t1) t1=a[i].second;
    }
    s1[++ls1][0]=t0;
    s1[ls1][1]=t1;
    s1[ls1][2]=0;
    t0=y0; t1=y1;
    for(int i=mid2+1;i<=r;i++){
        s2[++ls2][0]=t0;
        s2[ls2][1]=t1;
        s2[ls2][2]=a[i].first;
        if(a[i].second<=ymid && a[i].second>t0) t0=a[i].second;
        if(a[i].second>ymid && a[i].second<t1) t1=a[i].second;
    }
    s2[++ls2][0]=t0;
    s2[ls2][1]=t1;
    s2[ls2][2]=w;
    S1.clear();
    S2.clear();
    S3.clear();
    int now1=1,now2=1;
    for(int i=1;i<=ls2;i++){
        while(!S3.empty() && s2[S3.front()][1]-s2[S3.front()][0]+s2[S3.front()][2]<s2[i][1]-s2[i][0]+s2[i][2])
            S3.pop_front();
        S3.push_front(i);
    }
    int res=0;
    for(int i=1;i<=ls1;i++){
        while(now1<=ls2 && s2[now1][0]<=s1[i][0]){
            while(!S1.empty() && s2[S1.front()][1]+s2[S1.front()][2]<s2[now1][1]+s2[now1][2])
                S1.pop_front();
            S1.push_front(now1++);
        }
        while(now2<=ls2 && s2[now2][1]>=s1[i][1]){
            while(!S2.empty() && s2[S2.front()][2]-s2[S2.front()][0]<s2[now2][2]-s2[now2][0])
                S2.pop_front();
            S2.push_front(now2++);
        }
        while(!S1.empty() && s2[S1.back()][1]>=s1[i][1]) S1.pop_back();
        while(!S2.empty() && s2[S2.back()][0]<=s1[i][0]) S2.pop_back();
        while(!S3.empty() && (s2[S3.back()][0]<=s1[i][0] || s2[S3.back()][1]>=s1[i][1])) S3.pop_back();
        res=max(res,s1[i][1]-s1[i][0]+s2[min(now1-1,now2-1)][2]-s1[i][2]);
        if(!S1.empty()) res=max(res,s2[S1.back()][1]-s1[i][0]+s2[S1.back()][2]-s1[i][2]);
        if(!S2.empty()) res=max(res,s1[i][1]-s2[S2.back()][0]+s2[S2.back()][2]-s1[i][2]);
        if(!S3.empty()) res=max(res,s2[S3.back()][1]-s2[S3.back()][0]+s2[S3.back()][2]-s1[i][2]);
    }
    res=max(res,max(res1,res2));
    return res;
}

int solve(){
    w0=w/2;
    sort(a+1,a+n+1,cmp2);
    return gao(1,n,0,h);
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d%d",&w,&h,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].first,&a[i].second);
    int ans1=solve()*2;
    swap(w,h);
    for(int i=1;i<=n;i++) swap(a[i].first,a[i].second);
    int ans2=solve()*2;
    printf("%d\n",max(ans1,ans2));
    return 0;
}