题目描述
Problem Description
Given an $N \times M$ rectangular wheat field. Each area of the field grows a certain amount of grass. Initially, the grass amount in all areas is $1$.
For $K$ days, circular UFOs will land on the field and draw circles. On the morning of the $i$-th day, a UFO with a radius of $R_i$ will land at area $(X_i, Y_i)$, affecting all areas within a radius of $R_i$ centered at that area. If an area $(x, y)$ is affected and $(X_i - x)^2 + (Y_i - y)^2 \leq R_i^2$, the grass amount in that area will be reduced to $0$. At the beginning of each new day, the grass amount in each area increases by $1$.
Determine the total grass amount in all areas by the evening of the $K$-th day.
Input Format
The first line contains two positive integers $N$ and $M$, representing the dimensions of the field.
The second line contains a positive integer $K$, representing the number of days.
The next $K$ lines, where the $i$-th line contains three positive integers $X_i$, $Y_i$, and $R_i$, representing the landing area and the radius of the UFO.
Output Format
Output the total amount of grass.
Sample Input and Output
Input Sample #1
6 6
3
4 4 2
3 3 2
2 4 1
Output Sample #1
68
Input Sample #2
100 100
2
50 50 49
30 30 29
Output Sample #2
9534
Input Sample #3
33333 44444
1
11111 22222 9999
Output Sample #3
1167355751
Notes
Sample 1 Explanation
The field at the end of the first day:
| $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
|---|---|---|---|---|---|
| $1$ | $1$ | $1$ | $\red 0$ | $1$ | $1$ |
| $1$ | $1$ | $\red 0$ | $\red 0$ | $\red 0$ | $1$ |
| $1$ | $\red 0$ | $\red 0$ | $\red 0$ | $\red 0$ | $\red 0$ |
| $1$ | $1$ | $\red 0$ | $\red 0$ | $\red 0$ | $1$ |
| $1$ | $1$ | $1$ | $\red 0$ | $1$ | $1$ |
The field at the end of the second day:
| $2$ | $2$ | $\red 0$ | $2$ | $2$ | $2$ |
|---|---|---|---|---|---|
| $2$ | $\red 0$ | $\red 0$ | $\red 0$ | $2$ | $2$ |
| $\red 0$ | $\red 0$ | $\red 0$ | $\red 0$ | $\red 0$ | $2$ |
| $2$ | $\red 0$ | $\red 0$ | $\red 0$ | $1$ | $1$ |
| $2$ | $2$ | $\red 0$ | $1$ | $1$ | $2$ |
| $2$ | $2$ | $2$ | $1$ | $2$ | $2$ |
The field at the end of the third day:
| $3$ | $3$ | $1$ | $\red 0$ | $3$ | $3$ |
|---|---|---|---|---|---|
| $3$ | $1$ | $\red 0$ | $\red 0$ | $\red 0$ | $3$ |
| $1$ | $1$ | $1$ | $\red 0$ | $1$ | $3$ |
| $3$ | $1$ | $1$ | $1$ | $2$ | $2$ |
| $3$ | $3$ | $1$ | $2$ | $2$ | $3$ |
| $3$ | $3$ | $3$ | $2$ | $3$ | $3$ |
Thus, the total grass amount is $68$ units.
Data Size and Constraints
For $20\%$ of the data, $N, M \leq 1000$.
For $100\%$ of the data, $1 \leq N, M \leq 10^5$, $1 \leq K \leq 100$, $1 < X_i < N$, $1 < Y_i < M$, $1 \leq R_i \leq \min(X_i - 1, Y_i - 1, N - X_i, M - Y_i)$.
Notes
This problem's score is set according to the original COCI contest, with a maximum score of $110$.
The problem is translated from COCI2018-2019 CONTEST #3 T4 NLO.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分