2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it

链接：https://www.nowcoder.com/acm/contest/163/F

来源：牛客网

2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it

时间限制：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 (x_c, y_c) 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.

输入描述:

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 10⁴; 1 ≤ q ≤ 200), as mentioned above.

The next q lines, each lines contains three integers x

_c

, y

_c

 and r (0 ≤ x

_c

 < N; 0 ≤ y

_c

 < M; 0 ≤ r ≤ 10

⁵

), as mentioned above.

输出描述:

For each test case, output one number.

<!--
-->

输入例子:

2

39 49 2

12 31 6

15 41 26

1 1 1

0 0 1

输出例子:

729

0

-->

示例1

输入

复制

2

39 49 2

12 31 6

15 41 26

1 1 1

0 0 1

输出

复制

729

0

---

题意还是比较简单的，给你n和m的格子让你去画圆，如果这个点在圆内，就要被染色，问你还剩多少点没有被染色

这个题目可以直接暴力扫描线，也就成了维护线段的并

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+;

vector<pair<int,int> >V[N];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        for(int i=; i<N; i++)V[i].clear();

        int n,m,q;

        scanf("%d%d%d",&n,&m,&q);

        for(int j=,x,y,r; j<q; j++)

        {

            scanf("%d%d%d",&x,&y,&r);

            for(int i=max(,y-r),d; i<=min(m-,y+r); i++)

                d=(sqrt(r*r-(y-i)*(y-i)+1e-)),V[i].push_back(make_pair(max(,x-d),min(x+d,n-)));

        }

        int s=n*m;

        for(int i=; i<m; i++)

        {

            int l=V[i].size();

            if(l>)

            {

                sort(V[i].begin(),V[i].end());

                int r=-;

                for(auto X:V[i])

                {

                    if(X.second<=r)continue;

                    if(X.first>r) s-=X.second-X.first+;

                    else s-=X.second-r;

                    r=X.second;

                }

            }

        }

        cout<<s<<"\n";

    }

    return ;

}

2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it的相关教程结束。