2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it (扫描线)
链接:https://ac.nowcoder.com/acm/contest/163/F来源:牛客网
时间限制:C/C++ 3秒,其他语言6秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
There is a matrix A that has N rows and M columns. Each grid (i,j)(0 ≤ i < N, 0 ≤ j < M) is painted in white at first.
Then we perform q operations:
For each operation, we are given (xc, yc) and r. We will paint all grids (i, j) that meets (i−xc)2+(j−yc)2≤r\sqrt{(i-x_c)^2 + (j-y_c)^2} \leq r(i−xc)2+(j−yc)2≤r to black.
You need to calculate the number of white grids left in matrix A.
输入描述:
The first line of the input is T(1≤ T ≤ 40), which stands for the number of test cases you need to solve.The first line of each case contains three integers N, M and q (1 ≤ N, M ≤ 2 x 104; 1 ≤ q ≤ 200), as mentioned above.The next q lines, each lines contains three integers xc, yc and r (0 ≤ xc < N; 0 ≤ yc < M; 0 ≤ r ≤ 105), as mentioned above.
输出描述:
For each test case, output one number.
示例1
输入
[复制](javascript:void(0)