bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 曼哈顿生成树

　　大致题意：统计平面上由曼哈顿距离小于等于c的点对组成联通块的个数。

　　曼哈顿生成树的模板题。有关讲解：http://blog.csdn.net/acm_cxlove/article/details/8890003

　　

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define MAXN 100100

#define MAXE MAXN*8

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3fLL

typedef long long qword;

int n,m;

struct edge

{

        int x,y;

        qword d;

}e[MAXE];

int tope=-;

bool cmp_d(edge e1,edge e2)

{

        return e1.d<e2.d;

}

int uf[MAXN];

int get_fa(int now)

{

        return uf[now]==now ? now : uf[now]=get_fa(uf[now]);

}

int comb(int x,int y)

{

        x=get_fa(x);

        y=get_fa(y);

        if (x==y)return false;

        uf[x]=y;

        return true;

}

struct point

{

        qword x,y;

        int id;

}pl[MAXN];

bool cmp_x(point p1,point p2)

{

        if (p1.x==p2.x)return p1.y>p2.y;

        return p1.x>p2.x;

}

void rotate1()

{

        for (int i=;i<n;i++)

                pl[i].x=-pl[i].x;

}

void rotate2()

{

        for (int i=;i<n;i++)

                pl[i].y=-pl[i].y;

}

void rotate3()

{

        for (int i=;i<n;i++)

                swap(pl[i].x,pl[i].y);

}

qword h[MAXN],toph=-;

qword tarr[MAXN];

int tarr_id[MAXN];

void Add_tarr(int pos,qword v,int id)

{

        while (pos<MAXN)

        {

                tarr[pos]=min(tarr[pos],v);

                if (v==tarr[pos])tarr_id[pos]=id;

                pos+=pos&(-pos);

        }

}

pair<qword,int> Qry_tarr(int pos)

{

        pair<qword,int> ret;

        ret.first=INFL;

        while (pos)

        {

                ret.first=min(ret.first,tarr[pos]);

                if (ret.first==tarr[pos])

                        ret.second=tarr_id[pos];

                pos-=pos&(-pos);

        }

        return ret;

}

void work()

{

        int i,j;

        toph=;

        memset(tarr,0x3f,sizeof(tarr));

        for (i=;i<n;i++)

                h[++toph]=pl[i].x-pl[i].y;

        sort(h+,h+toph+);

        toph=unique(h+,h+toph+)-h-;

        sort(pl,pl+n,cmp_x);

        for (i=;i<n;i++)

        {

                pair<qword,int> pr;

                qword t=pl[i].x-pl[i].y;

                t=lower_bound(h+,h+toph+,t)-h;

                pr=Qry_tarr(t);

                if (pr.first!=INFL)

                {

                        e[++tope].x=pl[i].id;

                        e[tope].y=pr.second;

                        e[tope].d=pr.first-pl[i].x-pl[i].y;

                }

                Add_tarr(t,pl[i].x+pl[i].y,pl[i].id);

        }

}

int is_root[MAXN],uf_size[MAXN];

int main()

{

        freopen("input.txt","r",stdin);

        //freopen("output.txt","w",stdout);

        int i,j,k,x,y,z;

        scanf("%d%d",&n,&m);

        for (i=;i<n;i++)

        {

                scanf("%lld%lld",&pl[i].x,&pl[i].y);

                pl[i].id=i;

        }

        //

        work();

        //

        rotate3();

        work();

        rotate3();

        //

        rotate2();

        rotate3();

        work();

        rotate3();

        rotate2();

        //

        rotate2();

        work();

        rotate2();

        //

        rotate2();

        rotate1();

        work();

        rotate1();

        rotate2();

        //

        rotate1();

        rotate2();

        rotate3();

        work();

        rotate3();

        rotate2();

        rotate1();

        //

        rotate1();

        rotate3();

        work();

        rotate3();

        rotate1();

        //

        rotate1();

        work();

        rotate1();

        sort(e,e+tope+,cmp_d);

        for (i=;i<=n;i++)uf[i]=i;

        for (i=;i<=tope && e[i].d<=m;i++)

        {

                comb(e[i].x,e[i].y);

        }

        int ans2=;

        for (i=;i<n;i++)

        {

                is_root[get_fa(i)]=;

                uf_size[uf[i]]++;

        }

        for (i=;i<n;i++)

                is_root[i]+=is_root[i-];

        for (i=;i<n;i++)

                ans2=max(ans2,uf_size[i]);

        printf("%d %d\n",is_root[n-],ans2);

        return ;

}