A5872. 「COCI 2018.12」NLO
编程题
省选/NOI-
知识点
题目描述
**译自 [COCI 2018/2019 Contest #3](https://hsin.hr/coci/archive/2018_2019/) T4「[NLO](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf)」**
Žabnik 村已经被不明飞行物（UFO）所创造的麦田怪圈所困扰了数年。其问题主要在夏季割草的时候显现出来。
麦田是一块 $N$ 行 $M$ 列的格子——左上角记为坐标 $(1,1)$，右下角记为坐标 $(N,M)$。一开始每块地上都有一单位的草。接下来 $K$ 天，圆形的 UFO 会登录在草地上并产生一个圆圈。第 $i$ 天早晨，一个半径为 $R_i$ 的 UFO 会登陆与位于 $(X_i, Y_i)$ 的草地上然后将其覆盖范围内的草都“割平”。或者说，如果一块坐标为 $(x,y)$ 的地满足 $(X_i-x)^2 + (Y_i-y)^2 \le R_i^2$，那么这块地的草的数量就会被归为 $0$。每过一天，每块草地的数量增加 $1$。
在第 $K$ 天晚上，当地人会将剩余的草全部收割，请问他们收割的草总量是多少？
Žabnik 村已经被不明飞行物（UFO）所创造的麦田怪圈所困扰了数年。其问题主要在夏季割草的时候显现出来。
麦田是一块 $N$ 行 $M$ 列的格子——左上角记为坐标 $(1,1)$，右下角记为坐标 $(N,M)$。一开始每块地上都有一单位的草。接下来 $K$ 天，圆形的 UFO 会登录在草地上并产生一个圆圈。第 $i$ 天早晨，一个半径为 $R_i$ 的 UFO 会登陆与位于 $(X_i, Y_i)$ 的草地上然后将其覆盖范围内的草都“割平”。或者说，如果一块坐标为 $(x,y)$ 的地满足 $(X_i-x)^2 + (Y_i-y)^2 \le R_i^2$，那么这块地的草的数量就会被归为 $0$。每过一天，每块草地的数量增加 $1$。
在第 $K$ 天晚上，当地人会将剩余的草全部收割，请问他们收割的草总量是多少？
输入格式
第一行两个正整数 $N,M$ 表示草地的行数和列数。
第二行一个正整数 $K$ 表示有 UFO 经过的天数。
接下来 $K$ 行，其第 $i$ 行包含三个正整数 $X_i, Y_i, R_i$，表示 UFO 登陆的位置以及半径。
第二行一个正整数 $K$ 表示有 UFO 经过的天数。
接下来 $K$ 行，其第 $i$ 行包含三个正整数 $X_i, Y_i, R_i$，表示 UFO 登陆的位置以及半径。
输出格式
一个整数，输出收割的草的总量。
输入输出样例
输入 #1
6 6 3 4 4 2 3 3 2 2 4 1
输出 #1
68
输入 #2
100 100 2 50 50 49 30 30 29
输出 #2
9534
输入 #3
33333 44444 1 11111 22222 9999
输出 #3
1167355751
说明/提示
对于 $20\%$ 的数据，保证 $N, M \le 1000$。
对于 $100\%$ 的数据，保证：
- $1\le N, M \le 10^5$
- $1\le K \le 100$
- $1 < X_i < N$
- $1 < Y_i < M$
- $1 \le R_i \le \min(X_i - 1, Y_i - 1, N - X_i, M - Y_i)$
对于 $100\%$ 的数据，保证：
- $1\le N, M \le 10^5$
- $1\le K \le 100$
- $1 < X_i < N$
- $1 < Y_i < M$
- $1 \le R_i \le \min(X_i - 1, Y_i - 1, N - X_i, M - Y_i)$