Description
A 国和 B 国是两个超级大国，长期处于冷战状态；
A 国在 B 国中设有 N 个情报站，编号为 1,2,3, …… ,N ，每个情报站有一个坐标 (Xi,Yi) 。但是， A 国的工作人员发现，每个情报站里都被埋上了炸弹！
这些炸弹非常特殊 ， 只要同时拆除其中的三个炸弹 ， 所有炸弹就都不会爆炸了。
由于各个情报站联络需要代价 ， 拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。
现在 A 国的指挥部门找到了你 ， 希望知道可能需要的最大代价和最小代价 。
N<=100000
Solution
- 画图可知求的是让三个点被围的最小矩形周长最大。
最大值：
- 直接找到所有点的xmax,xmin,ymax,ymin
- 由于三个点，控制四个边界，有一个点同时控制了两个边界，枚举这个点，再分别与另外两个边界找到max就好了。
- 关于点数：另外两个边界最多才两个点，保证了在三个点以内。而若只有一个点同时确定了两个边界，而这个矩形内没有点，画画图会发现只要有任意一个点在外面答案就会更大，所以一定有三个点。
- 然后ans=min(max(x-xmin,xmax-x)+max(y-ymin,ymax-y)
最小值：
- 一定有一个点同时控制两个边界，钦定这个点为左下角（旋转后也是一样的）。
- （1）剩下一个点控制右上角。
- （2）还有两个点分别控制右和上。
- （1）：枚举在左下角和右上角中间的点。找到对角方向x+y或-x-y最小的点（旋转一下即为左上角和右下角），计算答案。
- （2）：按x大到小，y大到小排序。以y为关键字记录最小的x+y，最小的x。
- 按顺序枚举左下角，查找在它上面的最小的x+y，保证在它右边。
- 用y更新在它下方的x+y，区间修改。具体来说用区间上记录的minx+y更新min(x+y)
- 再用x更新这一行的minx，单点修改。
- 注意：tag遍历之前一定要清空，防止用前面（横坐标更小）的x更新后面的y，这样不满足讨论的情况。
- 因为y只能和在它右边的x组合更新，所以确定了以上的顺序。
O（nlogn）
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 100005
#define maxm 7000005
#define maxx 1e8
#define inf 1e9
using namespace std;
struct node{int x,y;} a[maxn],t[maxn],tmp;
int cmp(node a,node b){return a.x>b.x||a.x==b.x&&a.y>b.y;}
int n,i,j,k,ans;
int tot,rt,tag[maxm],tx[maxm],ts[maxm],tl[maxm],tr[maxm];
void GETMAX(){
int xmax=-inf,ymax=-inf,xmin=inf,ymin=inf;
for(i=1;i<=n;i++){
xmax=max(xmax,a[i].x),xmin=min(xmin,a[i].x);
ymax=max(ymax,a[i].y),ymin=min(ymin,a[i].y);
}
ans=0;
for(i=1;i<=n;i++)
ans=max(ans,max(a[i].x-xmin,xmax-a[i].x)+max(a[i].y-ymin,ymax-a[i].y));
printf("%d
",2*ans);
}
void rotate(){
for(int i=1;i<=n;i++){
swap(a[i].x,a[i].y);
a[i].x=-a[i].x;
}
}
int newnode(){
tot++;
tag[tot]=tx[tot]=ts[tot]=inf; tl[tot]=tr[tot]=0;
return tot;
}
void downtag(int x){
ts[x]=min(ts[x],tx[x]+tag[x]);
if (tl[x]) tag[tl[x]]=min(tag[tl[x]],tag[x]);
if (tr[x]) tag[tr[x]]=min(tag[tr[x]],tag[x]);
tag[x]=inf;
}
int find(int x,int l,int r,int ll,int rr){
if (!x) return inf;
if (tag[x]<inf) downtag(x);
if (l>rr||r<ll) return inf;
if (ll<=l&&r<=rr) return ts[x];
int mid=floor(1.0*(l+r)/2);
int tmp=min(find(tl[x],l,mid,ll,rr),find(tr[x],mid+1,r,ll,rr));
if (tl[x]) ts[x]=min(ts[x],ts[tl[x]]);
if (tr[x]) ts[x]=min(ts[x],ts[tr[x]]);
return tmp;
}
void changes(int &x,int l,int r,int ll,int rr,int p){
if (!x) x=newnode();
if (tag[x]<inf) downtag(x);
if (l>rr||r<ll) return;
if (ll<=l&&r<=rr) {
tag[x]=p; downtag(x);
return;
}
int mid=floor(1.0*(l+r)/2);
changes(tl[x],l,mid,ll,rr,p);
changes(tr[x],mid+1,r,ll,rr,p);
ts[x]=min(ts[tl[x]],ts[tr[x]]);
}
void changex(int &x,int l,int r,int p,int q){
if (!x) x=newnode();
if (tag[x]<inf) downtag(x);
tx[x]=q;
if (l==r) return;
int mid=floor(1.0*(l+r)/2);
if (p<=mid) changex(tl[x],l,mid,p,q);
else changex(tr[x],mid+1,r,p,q);
}
int get(int x,int l,int r,int ll,int rr){
if (!x) return inf;
if (l>rr||r<ll) return inf;
if (ll<=l&&r<=rr) return tx[x];
int mid=floor(1.0*(l+r)/2);
return min(get(tl[x],l,mid,ll,rr),get(tr[x],mid+1,r,ll,rr));
}
void DOIT(){
sort(a+1,a+1+n,cmp);
tot=0; rt=newnode();
for(i=1;i<=n;i++) {
ans=min(ans,find(rt,-maxx,maxx,a[i].y,maxx)-a[i].x-a[i].y);
changes(rt,-maxx,maxx,-maxx,a[i].y,a[i].y);
changex(rt,-maxx,maxx,a[i].y,a[i].x);
}
}
int mi1[maxn],mi2[maxn];
void DUIJIAO(){
sort(a+1,a+1+n,cmp);
tot=0; rt=newnode();
for(i=1;i<=n;i++) {
mi1[i]=get(rt,-maxx,maxx,a[i].y,maxx);
changex(rt,-maxx,maxx,a[i].y,a[i].x+a[i].y);
}
tot=0; rt=newnode();
for(i=n;i>=1;i--) {
mi2[i]=get(rt,-maxx,maxx,-maxx,a[i].y);
changex(rt,-maxx,maxx,a[i].y,-a[i].x-a[i].y);
}
for(i=1;i<=n;i++)
ans=min(ans,mi1[i]+mi2[i]);
}
void GETMIN(){
ans=inf;
for(int cntf=0;cntf<4;cntf++){
DOIT();
rotate();
}
DUIJIAO();
rotate();
DUIJIAO();
printf("%d
",2*ans);
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
GETMAX();
GETMIN();
}