[USACO08OPEN] Cow Neighborhoods G

题目描述

了解奶牛的人都知道奶牛是如何组成「奶牛社区」的。他们观察了 Farmer John 的 $N$ 头奶牛(编号为 $1 \sim N$),它们在 $X$ 和 $Y$ 坐标范围为 $1$ 的牧场上放牧,每头奶牛都在自己唯一的整数直线坐标上。 如果满足以下两个标准中的至少一个,则两头奶牛是邻居: 1. 两只奶牛的曼哈顿距离不超过 $C$,即 $|X_i - x_i| + |Y_i - y_i| \leq C$; 2. 两只奶牛有共同的邻居。即存在一只奶牛 $k$,使 $i$ 与 $k$,$j$ 与 $k$ 均同属一个群。 给定奶牛的位置和距离 $C$,确定「奶牛社区」的数量和最大的「奶牛社区」中的奶牛数量。 例如,考虑下面的牧场。 当 $C = 4$ 时,这个牧场有四个社区:左边的一个大社区,两个大小为 1 的社区,右边有一个巨大的社区,里面有 $60$ 头不同的奶牛。 ```text .....................................*................. ....*...*..*.......................***................. ......*...........................****................. ..*....*..*.......................*...*.******.*.*..... ........................*.............***...***...*.... *..*..*...*..........................*..*...*..*...*... .....................................*..*...*..*....... .....................................*..*...*..*....... ...*................*.................................. .*..*............................*.*.*.*.*.*.*.*.*.*.*. .*.....*..........................*.*.*.*.*.*.*.*.*.*.* ....*.................................................. ```

输入输出格式

输入格式


第 $1$ 行包含两个用空格分隔的整数 $N, C$。 第 $2$ 到第 $N + 1$ 行每行包含两个用空格分隔的整数 $X_i, Y_i$,表示一头牛的坐标。

输出格式


共一行,为两个用空格分隔的整数,为「奶牛社区」的数量和最大的「奶牛社区」内牛的数量。

输入输出样例

输入样例 #1

4 2 
1 1 
3 3 
2 2 
10 10 

输出样例 #1

2 3 

说明

### 样例说明 #1 样例中有 $2$ 个社区,一个由前三头奶牛组成,另一个是最后一头奶牛。因此,最大的社区大小为 $3$。 ### 数据范围与约定 对于 $100\%$ 的数据,$1 \leq N \leq 10^5$,$1 \leq C \leq 10^9$,$1 \leq X_i, Y_i \leq 10^9$,$X_i, Y_i$ 均为整数。