bzoj 1604 [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居（set+并查集）

2023-01-27 21:22:43

Description

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的：

1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C.

2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群．

给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛

Input

第1行输入N和C，之后N行每行输入一只奶牛的坐标．

Output

仅一行，先输出牛群数，再输出最大牛群里的牛数，用空格隔开．

Sample Input

4 2
1 1
3 3
2 2
10 10

* Line 1: A single line with a two space-separated integers: the
number of cow neighborhoods and the size of the largest cow
neighborhood.

Sample Output

2 3

OUTPUT DETAILS:
There are 2 neighborhoods, one formed by the first three cows and
the other being the last cow. The largest neighborhood therefore
has size 3.

HINT

Source

Gold

【思路】

Set+并查集

曼哈顿距离分为以下情况

　　　　X-x+Y-y -> (X+Y)-(x+y)

　　　　X-x+y-Y -> (X-Y)-(x-y)　　

　　　　x-X+Y-y -> -( (X-Y)-(x-y) )　　

　　　　x-X+y-Y -> -( (X+Y)-(x+y) )

　　这四种情况，我们可以发现，答案就是

　　　　max( |(X+Y)-(x+y)|, |(X-Y)-(x-y)| )

　　于是把每个点变为(x+y,x-y) 并将x从小到大排序

　　维护一个队列使得front~i区间x坐标的差均小于c

　　用set维护队列元素中的y，如果i在set中的前驱或后继与i的y之差小于c则合并集合。

【代码】

 #include<set>

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int N = 1e5+;

 const int INF = 1e9+1e9+;

 struct Node{

     int x,y;

     bool operator < (const Node& rhs) const{

         return x<rhs.x;

     }

 }a[N];

 int n,c,p[N],sum[N],ans,mx;

 multiset<Node> S;

 multiset<Node> ::iterator it;

 int ifind(int u) {

     return u==p[u]? u:p[u]=ifind(p[u]);

 }

 void unit(int x,int y) {

     x=ifind(x),y=ifind(y); if(x!=y) p[x]=y;

 }

 void read(int& x) {

     char c=getchar(); int f=; x=;

     while(!isdigit(c)){if(c=='-')f=-; c=getchar();}

     while(isdigit(c)) x=x*+c-'',c=getchar();

     x*=f;

 }

 int main() {

     read(n),read(c);

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

     int x,y;

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

         read(x),read(y);

         a[i].x=x+y,a[i].y=x-y;

     }

     sort(a+,a+n+);

     S.insert((Node){INF,}),S.insert((Node){-INF,});

     int front=;

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

         while(a[i].x-a[front].x>c) {

             S.erase(S.lower_bound((Node){a[front].y,front}));

             ++front;

         }

         it=S.lower_bound((Node){a[i].y,i});

         Node r=*it,l=*(--it);

         if((LL)r.x-(LL)a[i].y<=c) unit(r.y,i);

         if((LL)a[i].y-(LL)l.x<=c) unit(l.y,i);

         S.insert((Node){a[i].y,i});

     }

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

         sum[ifind(i)]++;

         if(sum[ifind(i)]==) ans++;

     }

     for(int i=;i<=n;i++) mx=max(mx,sum[i]);

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

     return ;

 }

码农公寓