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

时间:2021-11-26 19:42:07

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)

2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it (扫描线)的更多相关文章

  1. 2018 ACM 国际大学生程序设计竞赛上海大都会部分题解

    题目链接 2018 ACM 国际大学生程序设计竞赛上海大都会 下午午休起床被同学叫去打比赛233 然后已经过了2.5h了 先挑过得多的做了 .... A题 rand x*n 次点,每次judge一个点 ...

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

    链接:https://www.nowcoder.com/acm/contest/163/F 来源:牛客网 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it 时间限制:C ...

  3. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers &lpar;数位DP&rpar;

    2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers (数位DP) 链接:https://ac.nowcoder.com/acm/contest/163/ ...

  4. 2018 ACM 国际大学生程序设计竞赛上海大都会赛

    传送门:2018 ACM 国际大学生程序设计竞赛上海大都会赛 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛2018-08-05 12:00:00 至 2018-08-05 17:00:0 ...

  5. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers (数位dp)

    题目链接:https://ac.nowcoder.com/acm/contest/163/J 题目大意:给定一个数N,求区间[1,N]中满足可以整除它各个数位之和的数的个数.(1 ≤ N ≤ 1012 ...

  6. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 A,D

    A链接:https://www.nowcoder.com/acm/contest/163/A Fruit Ninja is a juicy action game enjoyed by million ...

  7. 2018 ACM 国际大学生程序设计竞赛上海大都会 F - Color it &lpar;扫描线&rpar;

    题意:一个N*M的矩形,每个点初始都是白色的,有Q次操作,每次操作将以(x,y)为圆心,r为半径的区域涂成黑点.求最后剩余白色点数. 分析:对每行,将Q次操作在该行的涂色视作一段区间,那么该行最后的白 ...

  8. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛-B-Perfect Numbers(完数)

    题目描述 We consider a positive integer perfect, if and only if it is equal to the sum of its positive d ...

  9. 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛-K-Matrix Multiplication(矩阵乘法)

    题目描述 In mathematics, matrix multiplication or matrix product is a binary operation that produces a m ...

随机推荐

  1. pyqt信号和槽应用举例

    第一篇手写随笔. 项目的部分代码: 在子线程中改变主窗体的标签. class MyForm(QDialog): def __init__(self, parent=None): self.config ...

  2. php &colon; 基础&lpar;1&rpar;

    php基本语法形式 1.php的标记符 有以下形式: 形式1(推荐): <?php 这里要写符合php语法的语句 ?> 形式2: <script language="php ...

  3. 关于远程连接MySQL数据库的问题解决

    安装MySQL sudo apt-get install mysql-server 这个应该很简单了,而且我觉得大家在安装方面也没什么太大问题,所以也就不多说了,下面我们来讲讲配置. 配置MySQL ...

  4. Vue&period;js实现登录功能

    编写html,通过vue-resource.js库向后台提交数据 <!DOCTYPE html> <html lang="en"> <head> ...

  5. Java开发笔记(二十六)方法的输出参数

    前面介绍了方法的输入参数,与输入参数相对应的则为输出参数,输出参数也被称作方法的返回值,意思是经过方法的处理最终得到的运算数值.这个返回值可能是整型数,也可能是双精度数,也可能是数组等其它类型,甚至允 ...

  6. webbench安装使用

    简介 运行在linux上的一个性能测试工具 官网地址:http://home.tiscali.cz/~cz210552/webbench.html 如果不能打开的话,也可以直接到网盘下载:http:/ ...

  7. 汇编实验1(又是作业emm)

    实验任务:学会使用debug 1.使用Debug,将程序段写入内存: 机器码: b8 20 4e 05 16 14 bb 00 20 01 d8 89 c3 01 d8 b8 1a 00 bb 26 ...

  8. HDU 4549

    水题: 费马小定理+快速幂+矩阵快速幂 (第一次用到费马小定理) #include<bits/stdc++.h> using namespace std; typedef long lon ...

  9. Tomcat 在 Linux 上的安装和配置

    一.文件上传 先上传tomcat安装文件到Linux服务器 二.解压安装 使用以下命令解压安装包 .tar.gz 解压成功会生成一个文件夹 tomcat服务器运行时是需要JDK支持的,所以必须先安装好 ...

  10. C&num; CEF 封装UserControl

    using System; using System.Collections.Generic; using System.ComponentModel; using System.Drawing; u ...