算法分析

对不起我写这个的时候我们国庆节只放了一天假，所以我精神有点不正常… 大家忽略一些不太对的东西即可。这一定是我写的最哲学的一篇题解。

原理分析

曼哈顿距离：对于两点 p1(x1,y1),p2(x2,y2)，它们之间的曼哈顿距离为|x1-x2|+|y1-y2|
那么如何迅速地求曼哈顿距离最小生成树呢？我们找到一个点 p1, 然后以它为原点建立坐标轴，那么它只需要与这八个区域里的每个区域和它曼哈顿距离最近的点连一条边即可。

这是为什么呢？我们以 R2 区域为例，如果有两个点 P2 和 P3，P3 与 P1 的曼哈顿距离更小，那么：

dis(指曼哈顿距离）：dis(P1,P3)+dis(P3,P2) 小于等于 dis(P1,P2)+dis(P2,P3），当且仅当如图情况时，可以取到等号。所以嘛，基佬紫的 P2 和原谅绿的 P3 显然比 P2 和滑稽脸的 P1 关系好些，你们就不要打扰它们的友谊♂啦。

实现分析

那么根据边是无向的，对于每一个点 P1，我们就只考虑 R1,R2,R3,R4 啦。
比较好的一点是我们只考虑 R1, 然后：
1. 第一次操作不搞事
2. 第二次交换 x,y 坐标
3. 第三次将 x 坐标都变成相反数
4. 第四次交换 x,y 坐标
如图所示。

那么 R1 区域满足一个条件，在只考虑 R1,R2,R3,R4 时（即 x2>=x1) 对于 R1 区域的任意点 P2
y2-y1>=x2-x1（R3,R4 区域里 y2-y1 就是负数，x2-x1 还是整数）
即 y2-x2>=y1-x1
那么我们每次考虑的就是满足 x2>=x1 并且 y2-x2>=y1-x1 的点咯。
那么我们找的就是 y2-y1+x2-x1 最小，即 (y2+x2)-(y1+x2) 最小的点。
我们可以把所有点先按照横坐标排序，离散它们的 y2-x2，然后从左到右依次将点根据 y2-x2 的值丢进树状数组里，并维护它们 x2+y2 的最小值。每次查询 y2-x2>=y1-x1 的点里面 x2+y2 最小的点 P2 并连边，最后用 kurscal 求出最小生成树即可。

代码

（无论是时间还是长度还是空间复杂度都成功地踩了 boshi 大佬 2333）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
const int N=50005;
int n,cnt,m;
int b[N],f[N],mi[N],bh[N];
struct point{int x,y,id;}p[N];
bool cmp1(point a,point b){
    if(a.x==b.x)return a.y<b.y;
    else return a.x<b.x;
}
struct edge{int x,y,w;}e[N<<3];
bool cmp2(edge a,edge b){return a.w<b.w;}
void init(){
    int i;sort(p+1,p+1+n,cmp1);
    for(i=1;i<=n;++i)
        b[i]=p[i].y-p[i].x,bh[i]=-1,mi[i]=INT_MAX;
    sort(b+1,b+1+n);
    cnt=1;for(i=2;i<=n;++i)if(b[i]!=b[cnt])b[++cnt]=b[i];
}
int lowbit(int x){return x&(-x);}//以下是树状数组
int find(int x){
    int minn=INT_MAX,re=-1;
    while(x<=n){
        if(mi[x]<minn)minn=mi[x],re=bh[x];
        x+=lowbit(x);
    }
    return re;
}
void up(int x,int num,int ids){
    while(x){
        if(mi[x]>num)mi[x]=num,bh[x]=ids;
        x-=lowbit(x);
    }
}
void adde(int x,int y,int w){e[++m].x=x,e[m].y=y,e[m].w=w;}
int dis(int a,int b){return abs(p[a].x-p[b].x)+abs(p[a].y-p[b].y);}
int ff(int x){//并查集查找操作
    if(f[x]==x)return x;
    f[x]=ff(f[x]);return f[x];
}
void kurscal(){//最小生成树
    int i,r1,r2,ans=0,js=0;
    for(i=1;i<=n;++i)f[i]=i;
    sort(e+1,e+1+m,cmp2);
    for(i=1;i<=m;++i){
        r1=ff(e[i].x),r2=ff(e[i].y);
        if(r1!=r2)f[r1]=r2,ans+=e[i].w,++js;
        if(js==n-1)break;
    }
    printf("%d",ans);
}
int main(){
    int i,cas,kl,x;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d%d",&p[i].x,&p[i].y),p[i].id=i;
    for(cas=1;cas<=4;++cas){
        if(cas==2||cas==4)
            for(i=1;i<=n;++i)swap(p[i].x,p[i].y);
        else if(cas==3)
            for(i=1;i<=n;++i)p[i].x=-p[i].x;
        init();
        for(i=n;i>=1;--i){
            kl=lower_bound(b+1,b+1+cnt,p[i].y-p[i].x)-b;
            x=find(kl);
            if(x!=-1)adde(p[i].id,p[x].id,dis(i,x));
            up(kl,p[i].x+p[i].y,i);
        }
    }
    kurscal();
    return 0;
}