同poj3241

 

#include
     
      #include
      
       #define N 100010#define INF 0x3f3f3f3f#define LL long longusing namespace std;struct point{    int x,y,id;    bool operator<(const point &p) const    { return x==p.x?y
       
        
         0)    {        if (bit[x].w>w) bit[x].w=w,bit[x].p=p;        x-=x&-x;    }}void addedge(int a, int b, int w){    ++tot;    e[tot].a=a,e[tot].b=b,e[tot].w=w;}int dist(point a, point b){    return abs(a.x-b.x)+abs(a.y-b.y);}int main(){    int Case=0;    while(scanf("%d",&n)!=EOF&&n!=0)    {        tot=0;        for (int i=1;i<=n;i++)        {            scanf("%d%d",&p[i].x,&p[i].y);            p[i].id=i;        }        for (int dir=1;dir<=4;dir++)        {            if (dir==2||dir==4)                for (int i=1;i<=n;i++) swap(p[i].x,p[i].y);            else  if (dir==3)                for (int i=1;i<=n;i++) p[i].x=-p[i].x;            sort(p+1,p+n+1);            for (int i=1;i<=n;i++) a[i]=b[i]=p[i].y-p[i].x;            sort(b+1,b+1+n);            m=unique(b+1,b+1+n)-b-1;            for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;            for (int i=1;i<=m;i++) bit[i].w=INF,bit[i].p=-1;            for (int i=n;i>=1;i--)            {                int pos=query(a[i]);                if (pos!=-1) addedge(p[i].id,p[pos].id,dist(p[i],p[pos]));                update(a[i],p[i].x+p[i].y,i);            }        }        LL ans=0;        sort(e+1,e+tot+1);        for (int i=1;i<=n;i++) f[i]=i;        for (int i=1;i<=tot;i++)            if (find(e[i].a)!=find(e[i].b))        {            f[find(e[i].a)]=find(e[i].b);            ans+=e[i].w;        }        printf("Case %d: Total Weight = %lld\n",++Case,ans);    }    return 0;}