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+lYi - 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: thenumber of cow neighborhoods and the size of the largest cowneighborhood.
Sample Output
2 3
OUTPUT DETAILS:
There are 2 neighborhoods, one formed by the first three cows andthe other being the last cow. The largest neighborhood thereforehas size 3.
题解：
很早就开了这道题，一直没有A掉，今天课上无聊补了一发相关姿势，还是学了老半天才会，1A。
一般遇到这种二维的距离题，都可以在数学上做文章，此题用到曼哈顿距离，那么我们把公式|Xi-xi|+|Yi-yi|拆开，成了下面4个表达式。
(1)Xi-xi+Yi-yi
(2)Xi-xi+yi-Yi
(3)xi-Xi+Yi-yi
(4)xi-Xi+yi-Yi
那么其实可以将(1)(4)式合并为|(Xi+Yi)-(xi+yi)|，把(2)(3)式合并为|(Xi-Yi)-(xi-yi)|。
我们用A来代替x+y，B来代替x-y，则其实只要max(Ai-ai,Bi-bi)<=c就满足题目中距离要求了。
那么我们对于每个点（牛），都用A，B去表示。只需要先整体以A大小为标准进行一次排序，然后维护一个队列，使得队列中队首的A与队尾的A之差小于c即可，这样保证了队列中的点都是满足delta(A)不大于c的。同时利用set的平衡二叉树高效查询，维护队列中点的B值，遍历到一个点时，先得到满足当前情况的队列，然后得出以该点的B应该处于set中哪个位置，并与前后的B进行比较，满足delta(B)不大于c的就合并。
最后扫一下father数组就可以得答案了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <vector>
#define MAXN 100005
#define INF 0x3f3f3f3f
using namespace std;
long long int c,n;
long long int father[MAXN];
long long int total,head;
typedef struct node
{long long int x,y;bool operator <(const node&r)const{return x<r.x;}
}node;
multiset<node>S;
multiset<node>::iterator it;
node N[MAXN];
long long int find(long long int num)
{long long int root,tmp,now=num;while(father[now]!=now){now=father[now];}root=now;now=num;while(father[now]!=now){tmp=father[now];father[now]=root;now=tmp;}return root;
}
void unit(long long int a,long long int b)
{long long int fa=find(a),fb=find(b);if(fa!=fb)father[fa]=fb;
}
long long int num[MAXN];
int main()
{long long int x,y;cin >> n >> c;for(long long int i=1;i<=n;i++){scanf("%lld %lld",&x,&y);N[i].x=x+y,N[i].y=x-y;father[i]=i;}sort(N+1,N+n+1);S.insert(node{-INF,0}),S.insert(node{INF,0});head=1;for(long long int i=1;i<=n;i++){while(N[i].x-N[head].x>c){it=S.find(node{N[head].y,head});S.erase(it);head++;}it=S.lower_bound(node{N[i].y,i});node tmp1,tmp2;tmp1=*it;tmp2=*(--it);if(tmp1.x-N[i].y<=c)unit(tmp1.y,i);if(N[i].y-tmp2.x<=c)unit(tmp2.y,i);S.insert(node{N[i].y,i});}long long int out1=0,out2=0;for(long long int i=1;i<=n;i++)num[find(i)]++;for(long long int i=1;i<=n;i++){if(num[i]){out1++;out2=max(out2,num[i]);}}cout << out1 << " " << out2 << endl;return 0;
}