题目：
题意：有n*m个点全为白色，q个圆，将q个圆内所有的点都染成黑色，问最后剩下多少白色的点。
解题思路：每一行当做一个扫描线，扫描所有的圆，记录每一行在圆中的点即可，O(n*q)。
附ac代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 const int maxn = 2e5 + 10; 9 struct nod10 {11 int x;12 int y;13 int r;14 nod(){}15 bool operator < (const nod & b) const16 {17 if(x == b.x) return y < b.y;18 return x < b.x;19 }20 }nu[maxn],a[maxn];21 int main()22 {23 int t;24 int n, m, q;25 scanf("%d", &t);26 while(t--)27 {28 int ans = 0;29 scanf("%d %d %d", &n, &m, &q);30 for(int i = 1; i <= q; ++i)31 {32 scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].r);33 }34 int len = 0;35 for(int i = 0; i < n; ++i)36 {37 len = 0;38 for(int j = 1; j <= q; ++j)39 {40 int u = a[j].r * a[j].r - (a[j].x - i) * (a[j].x - i);41 if(u < 0) continue;42 u = sqrt(u);43 //printf("%d u\n", u);44 nu[++len].x = max(a[j].y - u, 0);45 nu[len].y = min(a[j].y + u, m - 1);46 //printf("%d len %d %d\n", len, nu[len].x, nu[len].y);47 }48 if(len == 0) continue;49 sort(nu + 1, nu + 1 + len);50 int lt = nu[1].x, rt = nu[1].y;51 for(int j = 2; j <= len; ++j)52 {53 if(nu[j].y < 0) continue;54 if(nu[j].x >= m) break;55 if(rt >= nu[j].x)56 {57 rt = max(rt,nu[j].y);58 }59 else60 {61 ans += rt - lt + 1;62 //printf("%d i %d %d lt %d rt\n", i, ans, lt, rt);63 lt = nu[j].x;64 rt = nu[j].y;65 }66 }67 ans += rt - lt + 1;68 //printf("%d i %d %d lt %d rt\n", i, ans, lt, rt);69 }70 printf("%d\n", n * m - ans);71 }72 return 0;73 }