Flood Fill

There are $M$ points on the plane. The taxicab distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $|x_1 - x_2| + |y_1 - y_2|$.

Two points are said to be directly connected if their taxicab distance is at most $D$. A group of points that can reach one another by following a chain of direct connections forms a single island. In other words, an island is a connected component of the "directly connected" relation.

For the given points, find the number of islands and the size of the largest island (the number of points it contains).

When $D = 1$, only points on the same cell or one orthogonal step apart are connected, which is the classic Flood Fill problem. This problem generalises that threshold to an arbitrary $D$.

The first line contains the number of points $M$ and the distance threshold $D$. ($1 \le M \le 100000$, $1 \le D \le 10^9$)

Each of the next $M$ lines contains the coordinates $X_i$ and $Y_i$ of a point. ($1 \le X_i, Y_i \le 10^9$)

The same coordinates may appear more than once; in that case the two points have taxicab distance $0$ and therefore always belong to the same island.

Print the number of islands and the size of the largest island on one line, separated by a space.

Because the coordinate range is very large, comparing every pair of points directly can be slow. If you change coordinates to $u = x + y$ and $v = x - y$, the taxicab distance becomes the Chebyshev distance $\max(|u_1 - u_2|,\ |v_1 - v_2|)$. Then two points are directly connected exactly when $|u_1 - u_2| \le D$ and $|v_1 - v_2| \le D$ — that is, when they fall inside a common axis-aligned square of side $D$ in the transformed coordinates.