Description：

如果两个点的曼哈顿距离不超过 $c$ ，那么他们在一群中，问有多少个群，最大的群中有多少个点。

$1\le n \le 10^5$

Solution：

和一个点曼哈顿距离不超过 $c$ 的范围如果画出来的话是一个菱形，这就非常不好处理，可以把它转成切比雪夫距离，及如果这个点的坐标为 $(x,y)$ ，那么把他转 $45^{\circ}$ 再放大，他的坐标就变成了 $(x+y,x-y)$ ，在这个坐标系下把所有在原坐标系中与该点曼哈顿距离 $\le k$ 的点组成了一个正方形，也就是说满足 $max(|x-x'|,|y-y'|)\le k$ ，这样限制只与 $x$ 和 $y$ 中较大的有关，于是可以把转换后的点按 $x$ 排序依次加入集合，并时刻保证集合中所有点 $x$ 坐标差的最大值不超过 $k$ ，这个可以维护一个队头指针，如果不合法则删除队头，队头指针右移，在集合内的点按 $y$ 排序，每次查询所有与 $y$ 距离不超过 $k$ 的点用并查集合并起来即可，但是不用查所有的，因为有些已经连起来了，其实只要查询前驱后继就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cstring>

using namespace std;

int n,c;

#define MAXN 100010

#define INF 0x3f3f3f3f

struct point

{

	int x,y,id;

	bool operator < (const point &b) const

	{

		if(y == b.y)return id < b.id;

		else return y < b.y;

	}

}p[MAXN];

bool cmp_x(point a,point b){return a.x < b.x;}

multiset<point> s;

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int siz[MAXN];

int ans1,ans2;

void merge(int a,int b)

{

	int p = find(a),q = find(b);

	if(p == q)return;

	f[p] = q;siz[q] += siz[p];

	--ans1;ans2 = max(ans2,siz[q]);

	return;

}

int main()

{

	scanf("%d%d",&n,&c);

	ans1 = n,ans2 = 1;

	int x,y;

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

	{

		scanf("%d%d",&x,&y);

		p[i].x = x + y;p[i].y = x - y;

	}

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

	{

		f[i] = i;siz[i] = 1;

		p[i].id = i;

	}

	sort(p + 1,p + 1 + n,cmp_x);

	s.insert((point){0,-INF,0});

	s.insert((point){0,INF,0});

	s.insert(p[1]);

	int l = 1,r = 1;

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

	{

		while(l <= r && p[i].x - p[l].x > c)

		{

			s.erase(s.find(p[l]));

			++l;

		}

		multiset<point>::iterator it = s.lower_bound(p[i]),rig = it,lef = --it;

		if(lef -> id != 0 && abs(p[i].y - lef -> y) <= c)merge(p[i].id,lef -> id);

		if(rig -> id != 0 && abs(p[i].y - rig -> y) <= c)merge(p[i].id,rig -> id);

		s.insert(p[i]);++r;

	}

	printf("%d %d\n",ans1,ans2);

	return 0;

}