4456：防空覆盖网
时间限制：4 S / 内存限制：65536 KB
AC：47 / Submit：92
| 问题描述 |
|---|
在一个a行b列的方格地图上有n门防空炮，每门防空炮由于型号不同，拥有各自的射程。当射程为p时，表示该防空炮能火力覆盖距离自身小于等于p范围的所有方格。 定义方格坐标(x1, y1)到(x2, y2)的距离是|x1-x2|+|y1-y2|，其中| |是数学上的绝对值运算。 由于飞机的速度很快，某个格子需要在至少m门防空炮的火力覆盖范围内，才能称为安全的格子。 求安全格子的数量。 |
| 输入描述 |
只有一组案例。 第一行是四个正整数a、b、n、m，表示地图是a行b列的，一共有n门防空炮，安全格子至少需要m门防空炮的火力覆盖。（a<=50，b<=50，n<=100000，m<=50000） 接下来是n行数据，每行数据由三个正整数x、y、p组成，代表一门防空炮的数据，表示该防空炮的坐标是(x, y)，即位于第x行第y列（地图的左上角称为第1行第1列），射程是p。（1<=x<=a，1<=y<=b，p<=50） |
| 输出描述 |
一个整数，表示地图中安全格子的数量。 不要换行。 |
| 样例输入复制样例 |
3 4 3 2 2 3 1 2 3 2 3 1 1 |
| 样例输出 |
7 |
| 提示说明 |
图中黄色的格子是安全的，一共7格。灰色的格子只有1门防空炮火力覆盖，白色的格子没有火力覆盖。
|
| 相关 |
