# [BZOJ1604]&&[Usaco2008 Open] Cow Neighborhoods 奶牛的邻居

## 描述 Description

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

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

4 2
1 1
3 3
2 2
10 10

## 样例输出 SampleOutput

2 3

BZOJ 1604

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=100005;
int i,j,t,n,m,l,r,k,z,y,x;
struct point
{
int x,y;
bool operator < (const point& tmp) const
{
return (x==tmp.x)?(y<tmp.y):(x<tmp.x);
}
}a[maxn];
multiset <point> s;
multiset <point>::iterator si;
int fa[maxn],ans[maxn];
int c,anss,ansm,top;
inline int getfa(int s)
{
if (fa[s]==s) return s;
fa[s]=getfa(fa[s]);
return fa[s];
}
inline void uno(int x,int y)
{
if (getfa(x)!=getfa(y)) fa[getfa(x)]=y;
}
int main()
{
s.clear();
scanf("%d%d",&n,&c);
for (i=1;i<=n;i++)
{
fa[i]=i;
scanf("%d%d",&x,&y);
a[i]=(point){x+y,x-y};
}
sort(a+1,a+n+1);
top=1;
s.insert((point){inf,0});
s.insert((point){-inf,0});
for (i=1;i<=n;i++)
{
while (a[i].x-a[top].x>c)
{
s.erase(s.lower_bound((point){a[top].y,top}));
top++;
}
si=s.lower_bound((point){a[i].y,i});
if (si!=s.end() && (*si).x-a[i].y<=c) uno((*si).y,i);
if (si!=s.begin())
{
si--;
if (a[i].y-(*si).x<=c) uno((*si).y,i);
}
s.insert((point){a[i].y,i});
}
anss=ansm=0;
for (i=1;i<=n;i++) ans[getfa(i)]++;
for (i=1;i<=n;i++) if (ans[i])
{
anss++;
ansm=max(ansm,ans[i]);
}
printf("%d %d\n",anss,ansm);
return 0;
}``````