#P5228. [SDOI2008]棋盘控制

[SDOI2008]棋盘控制

【题目】

在一个 NMN * M 的棋盘上,摆放着 KK 个棋子,一个棋子占据一个格子(可能有多个棋子占据同一个格子),控制棋盘上所有与它相距不超过 RR 的格子。两个格子 (X1,Y1)(X2,Y2)(X1,Y1)、(X2,Y2) 间的距离定义为 X1X2+Y1Y2|X1-X2|+|Y1-Y2|

试设计一个算法,计算出 KK 个棋子控制的格子总数。

【输入格式】

第一行共三个正整数 NMK (1N,M1081K105)N,M,K \ (1 \le N,M \le 10^8,1 \le K \le 10^5)

以下 KK 行,每行三个正整数 XYRX,Y,R ,分别表示棋子的所在行,所在列和控制范围。

【输出格式】

共一个数,即控制的格子总数。

4 4 3
1 1 1
3 1 1
3 3 1
10