奶牛社区
时间限制:1秒 内存限制:256M
【题目描述】
了解奶牛的人都知道奶牛是如何组成「奶牛社区」的。他们观察了FJ的 \(N\) 头奶牛(编号为 \(1∼N\)),每头奶牛都在自己唯一的平面坐标 \((x, y)\) 上。
如果满足以下两个标准中的至少一个,则两头奶牛是邻居:
1.两只奶牛的曼哈顿距离不超过 \(C\),即 \(|x_i−x_j|+|y_i−y_j|≤C\)
2.两只奶牛有共同的邻居。即存在一只奶牛 \(k\),使 \(i\) 与 \(k\),\(j\) 与 \(k\) 均同属一个群。
给定奶牛的位置和距离 \(C\),确定「奶牛社区」的数量和最大的「奶牛社区」中的奶牛数量。
【输入格式】
第 1 行包含两个用空格分隔的整数 \(N,C\)。
第 2 到第 \(N+1\) 行每行包含两个用空格分隔的整数 \(x_i,y_i\),表示一头牛的坐标。
【输出格式】
共一行,为两个用空格分隔的整数,为「奶牛社区」的数量和最大的「奶牛社区」内牛的数量。
【输入输出样例】
Input
4 2
1 1
3 3
2 2
10 10
Output
2 3
【样例解释】
样例中有 2 个社区,一个由前三头奶牛组成,另一个是最后一头奶牛。因此,最大的社区大小为 3。
【数据限制】
对于 \(100\%\) 的数据,\(1≤N≤10^5\),\(1≤C≤10^9\),\(1≤x_i,y_i≤10^9\)
【来源】
Mr.he**