【BZOJ】1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

【算法】并查集+平衡树+数学+扫描线

【题解】

经典曼哈顿距离转切比雪夫距离。

曼哈顿距离：S=|x1-x2|+|y1-y2|<=c

即：max(x1-x2+y1-y2,x1-x2-y1+y2,-x1+x2+y1-y2,-x1+x2-y1+y2)

令X1=x1+y1,Y1=x1-y1，则转化为

切比雪夫距离：S=max(|X1-X2|,|Y1-Y2|)<=c。

为什么要转化为切比雪夫距离？因为这种形式很容易操作。

想象两者的几何意义，哈夫曼距离<=c是竖着的正方形，而切比雪夫距离<=c是以一个点为中心的正方形（边平行于坐标轴）。

则问题转化为询问每个正方形，其内部包含的点，经典扫描线。

不过对于这题来讲，还需要一些小技巧来实现传递性。

首先一维排序，另一维用平衡树维护，也就是将排序后的点依次在平衡树上找到前驱和后继，然后再加入平衡树。

这样做就是对于每个点(x,y)，在<x的点中找到<y的第一个点和>y的第一个点连边并加入并查集（相等看x）。

从而，每个点只向前面连边，而y只向前面的相邻的点连边，最大限度避免重复统计。

复杂度O(n log n)。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<set>

using namespace std;

const int maxn=;

struct cyc{

    int y,d;

    bool operator < (const cyc &a)const{

        return y<a.y||(y==a.y&&d<a.d);

    }

};

struct node{int x,y;}a[maxn];

set<cyc>s;

set<cyc>::iterator it;

int fa[maxn],n,c,b[maxn];

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

bool cmp(node a,node b){return a.x<b.x;}

int main(){

    n=read();c=read();

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

        a[i].x=read();a[i].y=read();

        a[i]=(node){a[i].x+a[i].y,a[i].x-a[i].y};

    }

    sort(a+,a+n+,cmp);

    int l=;

    s.insert((cyc){a[].y,});

    for(int i=;i<=n;i++)fa[i]=i;

    for(int i=;i<=n;i++){//一边往前，一边两端

        while(a[i].x-a[l].x>c)s.erase((cyc){a[l].y,l}),l++;

        it=s.lower_bound((cyc){a[i].y,i});

        if(it!=s.end()&&it->y-a[i].y<=c&&find(i)!=find(it->d))fa[fa[i]]=fa[it->d];

        if(it!=s.begin()&&a[i].y-(--it)->y<=c&&find(i)!=find(it->d))fa[fa[i]]=fa[it->d];

        s.insert((cyc){a[i].y,i});

    }

    int mx=,num=;

    for(int i=;i<=n;i++)b[find(i)]++;

    for(int i=;i<=n;i++)if(b[i]){

        num++;

        if(b[i]>mx)mx=b[i];

    }

    printf("%d %d",num,mx);

    return ;

}

巴特西

【BZOJ】1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

最新文章

热门文章