P2906 [USACO08OPEN] Cow Neighborhoods G

People who know cows understand how they form "cow neighborhoods." They observed Farmer John’s $N$ cows (numbered $1$ through $N$) grazing on a pasture modeled as a plane with $X$ and $Y$ coordinates starting from $1$, where each cow is located at a unique integer lattice point. Two cows are neighbors if at least one of the following criteria holds: 1. Their Manhattan distance is at most $C$, i.e., $|X_i - X_j| + |Y_i - Y_j| \leq C$. 2. They share a common neighbor; that is, there exists a cow $k$ such that $i$ and $k$, and $j$ and $k$, both belong to the same group. Given the cows’ positions and the distance $C$, determine the number of "cow neighborhoods" and the number of cows in the largest "cow neighborhood." For example, consider the pasture below. When $C = 4$, this pasture has four neighborhoods: one large neighborhood on the left, two neighborhoods of size $1$, and a huge neighborhood on the right containing $60$ distinct cows. ```text .....................................*................. ....*...*..*.......................***................. ......*...........................****................. ..*....*..*.......................*...*.******.*.*..... ........................*.............***...***...*.... *..*..*...*..........................*..*...*..*...*... .....................................*..*...*..*....... .....................................*..*...*..*....... ...*................*.................................. .*..*............................*.*.*.*.*.*.*.*.*.*.*. .*.....*..........................*.*.*.*.*.*.*.*.*.*.* ....*.................................................. ```

The first line contains two space-separated integers $N, C$. Each of the next $N$ lines contains two space-separated integers $X_i, Y_i$, giving the coordinates of a cow.

Output a single line with two space-separated integers: the number of "cow neighborhoods" and the size of the largest "cow neighborhood."

Sample Explanation #1 There are $2$ neighborhoods in the sample: one formed by the first three cows, and the other by the last cow. Therefore, the largest neighborhood size is $3$. Constraints For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $1 \leq C \leq 10^9$, $1 \leq X_i, Y_i \leq 10^9$, and $X_i, Y_i$ are integers. Translated by ChatGPT 5