/ Vijos / 题库 /

奶牛社区

奶牛社区

时间限制: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**

信息

ID
2680
难度
9
分类
数据结构 | 平衡树 点击显示
标签
递交数
3
已通过
1
通过率
33%
被复制
1
上传者