2018上海大都会 F- color It

---

题目链接

---

时间限制：C/C++ 3秒，其他语言6秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

Problem Description

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 to black. You need to calculate the number of white grids left in matrix A.

Input

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.

Output

For each test case, output one number.

Sample intput

2
39 49 2
12 31 6
15 41 26
1 1 1
0 0 1

Sample Output

729
0

---

题意:

给定一个n×m的矩阵，在矩阵上画一些圆，求没有被圆覆盖的点的数目。

思路:

对于给的每个圆覆盖的范围，我们可以将其拆为在每一行的一段区间覆盖，那么最后对于每一行来说，我们只需要计算这一行的所有区间覆盖的范围即可。

代码:

 /***********************************************************************
  > Author: wood
  > Mail: cbcruel@gmail.com
  > Created Time: 2018年03月20日 星期二 17时51分10秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<ctime>
#include<string>

using namespace std;
typedef long long  LL;
typedef long long ll;
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const int maxn = 2e4+10;
const int mod = 998244353;
const LL INF = 1e18;
#define sqr(x) (x)*(x)
#define mp make_pair

vector<pair<int,int> > a[maxn];

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, m, q;
        scanf("%d %d %d", &n ,&m, &q);
        for(int i = 1; i <= n; ++i)
            a[i].clear();
        while(q--){
            int x, y, rr;
            scanf("%d %d %d", &x, &y, &rr);
            x++,y++;
            for(int i = max(1, x-rr); i <= min(n, x+rr); ++i){
                LL tmp = (LL)(sqr(1LL*rr) - sqr(1LL*(i-x)));
                int tt = sqrt(1.0*tmp+0.5);
                int l = max(1, y-tt);
                int r = min(m, y+tt);
                if(tmp >= 0)a[i].emplace_back(mp(l,r));
            }
        }LL ans = 0;
        for(int i = 1; i <= n; ++i){
            sort(a[i].begin(),a[i].end());
            int l = -1;
            for(auto &x : a[i]){
                l = max(l , x.first);
                if(l <= x.second) ans += x.second - l + 1;
                l = max(l, x.second+1);
            }
        }printf("%lld\n", 1LL*n*m-ans);
    }return 0;
}