清橙A1322. Bomb

清橙A1322. Bomb

问题描述 A国和B国是两个超级大国，长期处于冷战状态；
　　A国在B国中设有N个情报站，编号为1,2,3,……,N，每个情报站有一个坐标(Xi,Yi)。
　　但是，A国的工作人员发现，每个情报站里都被埋上了炸弹！
　　这些炸弹非常特殊，只要同时拆除其中的三个炸弹，所有炸弹就都不会爆炸了。
　　由于各个情报站联络需要代价，拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。
　　现在A国的指挥部门找到了你，希望知道可能需要的最大代价和最小代价。

虽然题目本身不难（然而我自己菜并没有想出怎么做），但是写的时候还是有点懵逼。

最大值的求法很简单，下面只考虑求最小值

实际上哈密顿路径之和就是包含了这三个点的最小矩形的周长。分两种情况，一种是其中两个点分别确定两个角，另一种是一个点确定一个角，另两个分别确定两条边。

对于第一种情况枚举中间这个点，对于第二种情况枚举角上的那个点，用线段树维护即可。顺序很重要，运用修改和查询的特性进行优化，很容易晕。

最后要注意的一点是，如果有点重复了的话，要特殊处理。

基本上就是个细节题吧。

#include<bits/stdc++.h>
using namespace std;int ti;#define mid ((l+r)>>1)
const int maxn=100100;
const int INF=1e9;
void chkmax(int &x,int y){x=x>y?x:y;
}
void chkmin(int &x,int y){x=x<y?x:y;
}
int Max(int x,int y){return x>y?x:y;
}
int Abs(int x){return x>0?x:-x;
}
int n;
struct node{int x,y,id;
}a[maxn];
bool operator != (const node &A,const node &B){return A.x!&#A.y!=B.y;
}
bool cmp(const node &A,const node &B){return A.y==B.y?A.x<B.x:A.y<B.y;
}
void solve_max(){int maxx=-INF,maxy=-INF,minx=INF,miny=INF;for(int i=1;i<=n;i++){chkmax(maxx,a[i].x),chkmax(maxy,a[i].y);chkmin(minx,a[i].x),chkmin(miny,a[i].y);}int ans=0;for(int i=1;i<=n;i++){chkmax(ans,Abs(a[i].x-minx)+Abs(a[i].y-miny));chkmax(ans,Abs(a[i].x-maxx)+Abs(a[i].y-maxy));chkmax(ans,Abs(a[i].x-minx)+Abs(a[i].y-maxy));chkmax(ans,Abs(a[i].x-maxx)+Abs(a[i].y-miny));}printf("%dn",ans*2);
}
int b[maxn];
namespace Min_normal{struct Tree{int x,y,ans;}tr[maxn<<2];void newnode(int h){tr[h].x=-INF,tr[h].y=-INF,tr[h].ans=-INF;}void check(int h,int x){if(x>tr[h].x){tr[h].x=x;chkmax(tr[h].ans,b[tr[h].x]+tr[h].y);}}void push_down(int h){if(tr[h].x<=-INF) return;check(h<<1,tr[h].x);check(h<<1|1,tr[h].x);tr[h].x=-INF;}void push_up(int h){chkmax(tr[h].y,tr[h<<1].y);chkmax(tr[h].y,tr[h<<1|1].y);chkmax(tr[h].ans,tr[h<<1].ans);chkmax(tr[h].ans,tr[h<<1|1].ans);}void Build_tree(int h,int l,int r){newnode(h);if(l==r) return;Build_tree(h<<1,l,mid);Build_tree(h<<1|1,mid+1,r);}void updataa(int h,int l,int r,int s,int t,int x){if(s<=l&&r<=t){check(h,x);return;}push_down(h);if(t<=mid) updataa(h<<1,l,mid,s,t,x);else if(s>mid) updataa(h<<1|1,mid+1,r,s,t,x);else{updataa(h<<1,l,mid,s,mid,x);updataa(h<<1|1,mid+1,r,mid+1,t,x);}push_up(h);}void updatab(int h,int l,int r,int p,int v){if(l==r){tr[h].y=v,tr[h].x=-INF;return;}push_down(h);if(p<=mid) updatab(h<<1,l,mid,p,v);else updatab(h<<1|1,mid+1,r,p,v);push_up(h);}int Query(int h,int l,int r,int s,int t){if(s<=l&&r<=t)return tr[h].ans;push_down(h);if(t<=mid) return Query(h<<1,l,mid,s,t);else if(s>mid) return Query(h<<1|1,mid+1,r,s,t);elsereturn Max(Query(h<<1,l,mid,s,mid),Query(h<<1|1,mid+1,r,mid+1,t));}int solve(){for(int i=1;i<=n;i++)b[i]=a[i].x;sort(b+1,b+n+1);for(int i=1;i<=n;i++)a[i].x=lower_bound(b+1,b+n+1,a[i].x)-b;sort(a+1,a+n+1,cmp);Build_tree(1,1,n);int ans=INF;for(int i=1;i<=n;i++){ti=i;chkmin(ans,b[a[i].x]+a[i].y-Query(1,1,n,1,a[i].x));updataa(1,1,n,a[i].x,n,a[i].x);updatab(1,1,n,a[i].x,a[i].y);}for(int i=1;i<=n;i++)a[i].x=b[a[i].x];return ans;}
}
namespace Min_extra{int sum1[maxn],sum2[maxn];int tr[maxn];void clear(){for(int i=1;i<=n;i++)tr[i]=-INF;}int Query(int x){int res=-INF;while(x){chkmax(res,tr[x]);x-=x&(-x);}return res;}void updata(int x,int v){while(x<=n){chkmax(tr[x],v);x+=x&(-x);}}void solve_mid(int *sum){for(int i=1;i<=n;i++)b[i]=a[i].x;sort(b+1,b+n+1);for(int i=1;i<=n;i++)a[i].x=lower_bound(b+1,b+n+1,a[i].x)-b;sort(a+1,a+n+1,cmp);clear();for(int i=1;i<=n;i++){sum[a[i].id]=b[a[i].x]+a[i].y-Query(a[i].x);updata(a[i].x,b[a[i].x]+a[i].y);}for(int i=1;i<=n;i++)a[i].x=b[a[i].x];}int solve(){int ans=INF;solve_mid(sum1);for(int i=1;i<=n;i++)a[i].x=-a[i].x,a[i].y=-a[i].y;solve_mid(sum2);for(int i=1;i<=n;i++)chkmin(ans,sum1[i]+sum2[i]);return ans;}
}
namespace Special{bool ok[maxn];int sum[maxn];int Unique(){int res=INF;sort(a+1,a+n+1,cmp);int cnt=0,num=0;for(int i=1;i<=n;i++){if(i==1||a[i]!=a[num]) a[++num]=a[i],cnt=1;else cnt++;if(cnt==2) ok[a[num].id]=1;if(cnt>=3) return 0;}n=num;Min_extra::solve_mid(sum);for(int i=1;i<=n;i++){a[i].x=-a[i].x;if(ok[a[i].id]) chkmin(res,sum[a[i].id]);}Min_extra::solve_mid(sum);for(int i=1;i<=n;i++){a[i].y=-a[i].y;if(ok[a[i].id]) chkmin(res,sum[a[i].id]);}Min_extra::solve_mid(sum);for(int i=1;i<=n;i++){a[i].x=-a[i].x;if(ok[a[i].id]) chkmin(res,sum[a[i].id]);}Min_extra::solve_mid(sum);for(int i=1;i<=n;i++){a[i].y=-a[i].y;if(ok[a[i].id]) chkmin(res,sum[a[i].id]);}for(int i=1;i<=n;i++)a[i].id=i;return res;}
}
int main(){
//	freopen("A1322.in","r",stdin);
//	freopen("A1322.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);a[i].id=i;}solve_max();int ans=INF;chkmin(ans,Special::Unique());chkmin(ans,Min_normal::solve());for(int i=1;i<=n;i++)a[i].x=-a[i].x;chkmin(ans,Min_normal::solve());for(int i=1;i<=n;i++)a[i].y=-a[i].y;chkmin(ans,Min_normal::solve());for(int i=1;i<=n;i++)a[i].x=-a[i].x;chkmin(ans,Min_normal::solve());chkmin(ans,Min_extra::solve());for(int i=1;i<=n;i++)a[i].y=-a[i].y;chkmin(ans,Min_extra::solve());printf("%dn",ans<<1);return 0;
}