基本是參照PKKJ寫的   Orz

/*
    題意：給出n<=100000個點坐標，求MST。邊權為點之間的曼哈頓距離
    題目給出重要提示：對于一個點O，在45度角度的范圍內，最多只有一條連出去的邊。 

    拓展這個提示，對于一個點O，45°的范圍內最多只有1條邊，8個方向只有8條
    8n條邊用kruskal可以解決
    由于是無向圖，只需要找到4個方向即可。通過旋轉90°，關于y=x翻轉做到這四個方向區域
    關于原點對稱的區域沒有訪問過。
    那怎么快速找到45°范圍內距離(xi,yi)最小的點呢？
    由于是45°范圍的點，有xj>xi,yj>yi，距離為xj+yj-xi-yi  所以用線段樹找x+y最小的點
    而且需要是在45°范圍內，還有y>yi
    先按照w=y-x從小到大排序，w相同的y大的優先
    檢查每個點，在線段樹中找到距離最小的點（沒有時為INF）
    然后再插入
*/
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

const int MAXN = 100010;
const int INF = 1000000000;

struct Edge
{
    int u,v,w;
    bool operator<(const Edge &B)const
    {
        return w<B.w;
    }
};

struct Point
{
    int x,y;
    Point(){}
    Point(int x,int y):x(x),y(y){}
};

struct SegTree
{
    int left,right;
    int Min,id;
};

Point pt[MAXN];
Edge edge[MAXN*10],*pE;
SegTree T[MAXN*3];
int fa[MAXN];
int yy[MAXN],ny[MAXN],idx[MAXN];

inline int dist(Point A,Point B)
{
    return abs(A.x-B.x)+abs(A.y-B.y);
}

bool cmp(const int &a,const int &b)
{
    int w1=pt[a].y-pt[a].x;
    int w2=pt[b].y-pt[b].x;
    if(w1==w2)return pt[a].y>pt[b].y;
    return w1<w2;
}

void build(int p,int left,int right)
{
    T[p].left=left;
    T[p].right=right;
    T[p].Min=INF;
    T[p].id=-1;
    if(left==right)return;
    int mid=(left+right)>>1;
    build(p<<1,left,mid);
    build((p<<1)|1,mid+1,right);
}

pair<int,int> query(int p,int y)
{
    if(T[p].right<y)return pair<int,int>(INF,-1);
    if(y<=T[p].left)return pair<int,int>(T[p].Min,T[p].id);
    return min(query(p<<1,y),query((p<<1)|1,y));
}

void insert(int p,int y,int val,int id)
{
    if(y<T[p].left||T[p].right<y)return;
    if(val<T[p].Min)T[p].Min=val,T[p].id=id;//邊插入邊更新
    if(T[p].left==T[p].right)return;//
    insert(p<<1,y,val,id);
    insert((p<<1)|1,y,val,id);
}

void add(int u,int v,int w)
{
    pE->u=u;
    pE->v=v;
    pE->w=w;
    pE++;
}
void make(int n)
{
    for(int i=0;i<n;i++)
    {
        idx[i]=i;
        yy[i]=pt[i].y;
    }
    sort(idx,idx+n,cmp);//對idx[]排序，這樣才不會破壞原來的pt[]
    sort(yy,yy+n);
    int nn=unique(yy,yy+n)-yy;
    for(int i=0;i<n;i++)
    {
        ny[i]=lower_bound(yy,yy+nn,pt[idx[i]].y)-yy;
    }
    build(1,0,nn-1);//
    for(int i=0;i<n;i++)
    {
        pair<int,int> res = query(1,ny[i]);//
        if(res.second!=-1)add(idx[i],idx[res.second],dist(pt[idx[i]],pt[idx[res.second]]));
        insert(1,ny[i],(pt[idx[i]].x+pt[idx[i]].y),i);
    }
}
void solve(int n)
{
    pE=edge;
    for(int k=0;k<4;k++)//坐標轉換  旋轉90； 旋轉90+關于y=x翻轉； 旋轉90
    {                //這樣得到的4個區域其關于原點的對稱的地方都是沒訪問過的，不會重復
        if(k>0)
        {
            for(int i=0;i<n;i++)
            {
                int x=-pt[i].y,y=pt[i].x;
                if(k==2)swap(x,y);
                pt[i]=Point(x,y);
            }
        }
        make(n);
    }
}

//kruskal
int find(int a)
{
    if(a!=fa[a])fa[a]=find(fa[a]);
    return fa[a];
}
void unin(int a,int b)
{
    a=find(a),b=find(b);
    if(a==b)return;
    fa[a]=b;
}
long long kruskal(int n)
{
    for(int i=0;i<n;i++)
        fa[i]=i;
    sort(edge,pE);
    long long ans = 0;
    int k=0;
    for(Edge *p=edge;p!=pE&&k<n-1;p++)
    {
        if(find(p->u)!=find(p->v))
        {
            unin(p->u,p->v);
            ans+=p->w;
            k++;
        }
    }
    return ans;
}
int main()
{
    //freopen("in","r",stdin);
    int n,t=1;
    while(scanf("%d",&n),n)
    {
        for(int i=0;i<n;i++)
            scanf("%d%d",&pt[i].x,&pt[i].y);
        solve(n);
        printf("Case %d: Total Weight = %lld\n",t++,kruskal(n));
    }
    return 0;
}