奶牛在草地上悠闲的吃着草，因为残象已使它们目不忍视，流言已使它们耳不忍闻。如果两个奶牛的曼哈顿距离 (|x,y 坐标差|的和) 小于等于 C, 它们处在同一组。问有多少个不同的组。

思路

注意到对于一个点 P, 曼哈顿距离小于等于 c 的点组成的集合是一个斜放的正方形，不方便后续操作，我们把它转正。怎么弄呢？对整个坐标系做变换
$$
\begin{bmatrix}
1 & -1 \\
1 & 1
\end{bmatrix} \tag{2}
$$
这是什么意思呢？如果在这个矩阵后面乘一个 2 行 1 列的矩阵表示一个 (x,y) 向量，那么相乘后的结果就是新的 (变换后的)(x,y) 向量。详情请参考矩阵乘法与向量组相关知识。
原来的 $(x,y)$全部变成 $(x\times (1,-1) , y\times(1,1) )$也就是 $(x-y,x+y)$
这里的矩阵只是为了更规范的描述这个变换。变换其实也可以想成是边把原来的 x 轴变成了 y=x 的直线，y 轴变成了 y=-x 的直线，对应的新坐标系中的点在原坐标系中的位置就是变换后的位置。
总之搞这么复杂只是为了达到把正方形搞正的目的。


接着我们考虑什么样的点属于一个组。变换后 x,y 坐标满足 $(x\in[x_0-c,x_0+c],y\in[y_0-c,y_0+c])$的点和 (x0,y0) 属于一个组。
于是我们可以按 y 坐标排序，利用扫描线法将当前所有 y 坐标相差小于等于 c 的点保存，每添加一个点与适当的点连线，用并查集维护同一个组的元素。


下面考虑如何维护当前的点集，并且高效的连线。
点集可以用multiset<pair<int,int> >维护 (不知为何 set 在洛谷上也可以 AC)，而连线时注意一下两条：
1. 新添加的点与点集中 x 坐标最小且与 x 属于同一组的点连线。
2. 新添加的点与点集中 x 坐标最大且与 x 属于同一组的点连线。
至于为什么这样就可以，而且必须连两条边，请大家琢磨琢磨。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>

#define MX 100005
#define oo 999999909

using namespace std;

typedef struct sdf
{
    int x,y;
}point;

point cow[MX];
int n,c;
int fa[MX];
int cnt[MX];
set<pair<int,int> > st;
set<int>ff;

int findfa(int x)
{
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}

inline bool cmp(point a,point b)
{
    return a.y<b.y;
}

void input()
{
    int x,y;
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        cow[i].x=x-y;
        cow[i].y=x+y;
    }
    sort(cow+1,cow+n+1,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
}

void work()
{
    int t;
    set<pair<int,int> >::iterator l,r;
    t=1;
    for(int i=1;i<=n;i++)
    {
        while(cow[i].y-cow[t].y>c)st.erase(make_pair(cow[t].x,t)),t++;
        l=st.lower_bound(make_pair(cow[i].x-c,0));
        r=st.lower_bound(make_pair(cow[i].x+c+1,0));
        if((l->first<=cow[i].x+c)&&(l!=st.end()))
            fa[findfa(l->second)]=findfa(i);
        if(r!=st.begin())
            if((--r)->first>=cow[i].x-c)fa[findfa(r->second)]=findfa(i);
        st.insert(make_pair(cow[i].x,i));
    }
    int mxpos=1,tot=0;
    for(int i=1;i<=n;i++)
    {
        cnt[findfa(i)]++;
        if(cnt[findfa(i)]>cnt[mxpos])mxpos=findfa(i);
        if(cnt[findfa(i)]==1)tot++;
    }
    cout<<tot<<" "<<cnt[mxpos]<<endl;
}

int main()
{
    input();
    work();
    return 0;
}