题目背景
一个恐怖组织在一座城市中安放了定时炸弹,其威力巨大,现在这里的警长想知道最坏的情况下会有多少街区受威胁。
题目描述
在一个城市有 N×M 个街区,每个街区由坐标描述,如图所示:
|
1 |
2 |
3 |
⋯ |
M |
1 |
(1,1) |
(1,2) |
(1,3) |
⋯ |
(1,M) |
2 |
(2,1) |
(2,2) |
(2,3) |
(2,M) |
3 |
(3,1) |
(3,2) |
(3,3) |
(3,M) |
⋮ |
|
⋱ |
|
N |
(N,1) |
(N,2) |
(N,3) |
⋯ |
(N,M) |
现在已知有一个恐怖组织在其中的一个街区安放了定时炸弹,其威力为 t,即所有到这个街区的直线距离小于等于 t 的街区都会受威胁,已知有 k 个可能的炸弹安放位置,现在这里的警长想知道最坏的情况下会有多少街区受威胁。
输入格式
第一行四个正整数 n,m,k,t。
接下来 k 行每行两个正整数 xi,yi,描述每个可能安放炸弹的街区。
输出格式
一个正整数为在最坏情况下有多少街区会受威胁。
4 5 3 2
1 2
3 4
4 5
11
提示
数据规模与约定
对于20%的数据 k=1。
对于 50% 的数据 1≤n,m≤1000,1≤k≤20,1≤t≤100。
对于 100% 的数据 1≤n,m≤105,1≤k≤50,t≤300。
fixed by @Cppsteve