描述 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 均同属一个群．
给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛
输入格式 InputFormat
第 1 行输入 N 和 C，之后 N 行每行输入一只奶牛的坐标．
输出格式 OutputFormat
仅一行，先输出牛群数，再输出最大牛群里的牛数，用空格隔开．
样例输入 SampleInput
4 2
1 1
3 3
2 2
10 10
样例输出 SampleOutput
2 3
将每个点转换为 (X+Y,X-Y)，则点 A,B 的曼哈顿距离变为 Max{|Ax-Bx|,|Ay-By|}。然后对于前半部分用排序 + 单调队列维护，后半部分用平衡树维护。答案用并查集维护。STL(multiset) 大法好。。。
#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;
}