题意：

给出$N*M$的区域，每个格子$(i,j)|(0≤i<N,0≤j<M)$最开始是白色的，现在有q次操作，每次操作对于给定的$(x_c,y_c)$和$r$，把满足$\sqrt{(i-x_c)^2+(j-y_c)^2}≤r$的格子涂成黑色。问在q次操作后区域中白色格子的个数。其中$1≤ N,M≤2*10^4,1≤q≤200$。

思路：

自己做的时候想到每个圆覆盖的整数点可以变成菱形，所以想到了矩形面积并，还觉得是不是要变换坐标系，整个都跑偏了…

其实考虑到数据范围很小，直接扫描线就可以了。

枚举$N$，遍历每个操作，可以求出这条扫描线与每个圆相交的区间，存入vector，再将这些区间按照左端点进行排序，然后问题就转化为这些区间覆盖的点的个数了，只要维护最右边的点R就可以了。

复杂度是$O(T*N*q)$，$10^8$似乎跑得蛮快啊？

写的时候仔细一点，注意我代码里注释的那个点。

代码：

struct node
{
    int l,r;
};
vector<node>v;
int r[210][3];
bool cmp(node x,node y)
{
    if(x.l!=y.l)return x.l<y.l;
    return x.r<y.r;
}
int main()
{
    int t,n,m,q;
    node temp;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&q);
        for(int i=0;i<q;i++)
            scanf("%d%d%d",&r[i][0],&r[i][1],&r[i][2]);
        int ans=n*m;
        for(int i=0;i<n;i++)
        {
            v.clear();
            for(int j=0;j<q;j++)
            {
                int lx=max(0,r[j][0]-r[j][2]),rx=min(n-1,r[j][0]+r[j][2]);
                if(i<lx||i>rx)continue;
                //printf("(%d,%d)(%d,%d)\n",i,j,lx,rx);
                int d=abs(i-r[j][0]);
                //printf("d:%d\n",d);
                int dd=(int)floor(sqrt(1.0*r[j][2]*r[j][2]-d*d));
                //printf("dd:%d\n",dd);
                temp.l=max(0,r[j][1]-dd);
                temp.r=min(m-1,r[j][1]+dd);
                //printf("%d %d\n",temp.l,temp.r);
                v.push_back(temp);
            }
            int len=v.size();
            if(len==0)continue;
            sort(v.begin(),v.end(),cmp);
            int R=v[0].r;
            ans-=v[0].r-v[0].l+1;
            for(int j=0;j<len;j++)
            {
                if(v[j].r<=R)continue;
                if(v[j].l<=R)ans-=v[j].r-R;
                //这里注意不用+1，因为之前已经算过R这个点了，因为这个WA了一发...
                else ans-=v[j].r-v[j].l+1;
                R=v[j].r;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}