P14010 Traverse Game

There are $n$ key points on the plane, each with integer coordinates in $[1,10^5]$. **It is guaranteed that these key points are four-connected, and that the plane becomes eight-connected after removing these key points.** Let $dis(i,j)$ denote the shortest path length from the $i$-th key point to the $j$-th key point, where a valid path is defined as follows: A path is a sequence of point pairs $(x_1,y_1),(x_2,y_2),\dots,(x_k,y_k)$, where the Manhattan distance between each pair of adjacent points is $1$, that is, $\forall i\in[1,n), |x_i-x_{i+1}|+|y_i-y_{i+1}|=1$, and every point in the sequence is a key point. The length of this path is defined as $k-1$, and the shortest path between two points is the shortest among all valid paths. Given $n$ and $k$, find how many pairs $(i,j)$ satisfy $dis(i,j)=k$.

The first line contains two integers, $n$ and $k$, representing the number of key points and the parameter $k$. The next $n$ lines each contain two integers, where the $i$-th line gives the coordinates $(x_i, y_i)$ of the $i$-th key point. It is guaranteed that the given points are distinct and satisfy the properties described above.

Output a single integer representing the answer.

### Data Range **This problem uses bundled tests.** | Subtask | $n\le$ | $k\le$ | Special Property | Score | |:---:|:-:|:-:|:-:|:-:| | $1$ | $10^3$ | $10^3$ | None | $15$ | | $2$ | $10^5$ | $10$ | None | $15$ | | $3$ | $10^5$ | $10^5$ | All key points form a rectangle | $20$ | | $4$ | $10^5$ | $10^5$ | No $2\times 2$ square is fully occupied by key points | $20$ | | $5$ | $10^5$ | $10^5$ | None | $30$ | - For $100\%$ of the data, it is guaranteed that $1\le n,k,x_i,y_i\le 10^5$. Translated by ChatGPT 4.1