[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$ 均为整数。