P2074 Danger Zone

A terrorist organization has planted a time bomb in a city, with great destructive power. The chief of police wants to know, in the worst case, how many blocks will be threatened.

In a city there are $N \times M$ blocks, each described by coordinates, as shown below: | | $1$ | $2$ | $3$ | $\cdots$ | $M$ | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $(1,1)$ | $(1,2)$ | $(1,3)$ | $\cdots$ | $(1,M)$ | | $2$ | $(2,1)$ | $(2,2)$ | $(2,3)$ | $\cdots$ | $(2,M)$ | | $3$ | $(3,1)$ | $(3,2)$ | $(3,3)$ | $\cdots$ | $(3,M)$ | | $\vdots$ | | | | $\ddots$ | | | $N$ | $(N,1)$ | $(N,2)$ | $(N,3)$ | $\cdots$ | $(N,M)$ | It is known that a terrorist organization has planted a time bomb in one of the blocks, with power $t$, meaning all blocks whose straight-line (Euclidean) distance to that block is less than or equal to $t$ will be threatened. There are $k$ possible bomb locations. The chief wants to know, in the worst case, how many blocks will be threatened.

The first line contains four positive integers $n, m, k, t$. The next $k$ lines each contain two positive integers $x_i, y_i$, describing each possible block where the bomb may be placed.

Output a single positive integer: the number of blocks that will be threatened in the worst case.

Constraints For $20\%$ of the testdata, $k = 1$. For $50\%$ of the testdata, $1 \le n, m \le 1000$, $1 \le k \le 20$, $1 \le t \le 100$. For $100\%$ of the testdata, $1 \le n, m \le 10^5$, $1 \le k \le 50$, $t \le 300$. fixed by @[$\color{#5EB95E}{\textsf{Cppsteve}}$](https://www.luogu.com.cn/user/479296) Translated by ChatGPT 5