危险区域

ID: 1015

远端评测题

1000ms

125MiB

难度: 2

上传者:

标签>

搜索

题目背景

一个恐怖组织在一座城市中安放了定时炸弹，其威力巨大，现在这里的警长想知道最坏的情况下会有多少街区受威胁。

在一个城市有 $N \times M$ 个街区，每个街区由坐标描述，如图所示：

	$1$	$2$	$3$	$\cdots$	$M$
$1$	$(1,1)$	$(1,2)$	$(1,3)$	$\cdots$	$(1,M)$
$2$	$(2,1)$	$(2,2)$	$(2,3)$		$(2,M)$
$3$	$(3,1)$	$(3,2)$	$(3,3)$		$(3,M)$
$\vdots$				$\ddots$
$N$	$(N,1)$	$(N,2)$	$(N,3)$	$\cdots$	$(N,M)$

现在已知有一个恐怖组织在其中的一个街区安放了定时炸弹，其威力为 $t$ ，即所有到这个街区的直线距离小于等于 $t$ 的街区都会受威胁，已知有 $k$ 个可能的炸弹安放位置，现在这里的警长想知道最坏的情况下会有多少街区受威胁。

第一行四个正整数 $n,m,k,t$ 。

接下来 $k$ 行每行两个正整数 $x_i,y_i$ ，描述每个可能安放炸弹的街区。

一个正整数为在最坏情况下有多少街区会受威胁。

数据规模与约定

对于 $20\%$ 的数据 $k=1$ 。

对于 $50\%$ 的数据 $1 \le n,m \le 1000$ ， $1 \le k \le 20$ ， $1\le t \le 100$ 。

对于 $100\%$ 的数据 $1 \le n,m \le 10^5$ ， $1 \le k \le 50$ ， $t \le 300$ 。