题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1604
题意：
平面直角坐标系中，有n个点（n <= 100000，坐标范围10^9）。
给定r，当两个点的曼哈顿距离<=r时，认为这两个点在同一个“群”中。
问你共有多少个群，以及点的数量最多的群有多少个点。
题解：
本题的核心在于：如何枚举一个点周围满足“曼哈顿距离<=r”的点。
由于 曼哈顿距离 = |x1 - x2| + |y1 - y2|。
x和y相互影响，不能单纯按x或y排序，枚举所有点总复杂度为O(N^2)。
所以要用到曼哈顿距离的另一种形式：
设X = x + y , Y = x - y
d（曼哈顿距离） = max(|X1-X2|, |Y1-Y2|)
将每个点的X = x + y，Y = x - y，这就将X与Y的关系分离开了。
将所有点按X排序。
当前考虑到点i。
用一个队列（X升序），保证队列中的所有X满足要求，否则不断删去队首。
用一个multiset（Y升序），找到i的前驱pre和后继suc，如果i与pre(或suc)的Y满足要求，则合并（并查集）。
最后统计一下每个群就好了。
AC Code:
// |x1-x2| + |y1-y2|
// | (x1+y1) - (x2+y2) |
// | (x1-y1) - (x2-y2) |
// X = x + y
// Y = x - y
// d = max(|X1-X2|, |Y1-Y2|) <= r
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#define MAX_N 100005
#define INF 100000000 using namespace std; struct Coor
{
int x;
int y;
int idx;
Coor(int _x,int _y,int _idx)
{
x=_x;
y=_y;
idx=_idx;
}
Coor(){}
friend bool operator < (const Coor &a,const Coor &b)
{
return a.y!=b.y?a.y<b.y:a.idx<b.idx;
}
}; int n,r;
int ans=;
int counter=;
int head=;
int par[MAX_N];
int cnt[MAX_N];
Coor c[MAX_N];
multiset<Coor> mst; inline bool cmp_x(const Coor &a,const Coor &b)
{
return a.x<b.x;
} void init_union_find()
{
for(int i=;i<n;i++)
{
par[i]=i;
}
} int find(int x)
{
return par[x]==x?x:par[x]=find(par[x]);
} void unite(int x,int y)
{
int px=find(x);
int py=find(y);
if(px==py) return;
par[px]=py;
} void read()
{
cin>>n>>r;
int a,b;
for(int i=;i<n;i++)
{
cin>>a>>b;
c[i].x=a+b;
c[i].y=a-b;
c[i].idx=i;
}
} void solve()
{
init_union_find();
sort(c,c+n,cmp_x);
mst.insert(Coor(,INF,));
mst.insert(Coor(,-INF,));
mst.insert(c[head]);
for(int i=;i<n;i++)
{
while(c[i].x-c[head].x>r)
{
mst.erase(c[head]);
head++;
}
multiset<Coor>::iterator it=mst.lower_bound(c[i]);
Coor suc=*it;
Coor pre=*--it;
if(c[i].y-pre.y<=r) unite(pre.idx,c[i].idx);
if(suc.y-c[i].y<=r) unite(suc.idx,c[i].idx);
mst.insert(c[i]);
}
memset(cnt,,sizeof(cnt));
for(int i=;i<n;i++)
{
int p=find(i);
if(cnt[p]==) counter++;
cnt[p]++;
ans=max(ans,cnt[p]);
}
} void print()
{
cout<<counter<<" "<<ans<<endl;
} int main()
{
read();
solve();
print();
}