链接:https://www.nowcoder.com/acm/contest/163/F
来源:牛客网
2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
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.
输入描述:
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
5
), 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
-->
输出
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的更多相关文章
-
2018 ACM 国际大学生程序设计竞赛上海大都会部分题解
题目链接 2018 ACM 国际大学生程序设计竞赛上海大都会 下午午休起床被同学叫去打比赛233 然后已经过了2.5h了 先挑过得多的做了 .... A题 rand x*n 次点,每次judge一个点 ...
-
2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it (扫描线)
2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it (扫描线) 链接:https://ac.nowcoder.com/acm/contest/163/F来源:牛客网 时间 ...
-
2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers (数位DP)
2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers (数位DP) 链接:https://ac.nowcoder.com/acm/contest/163/ ...
-
2018 ACM 国际大学生程序设计竞赛上海大都会赛
传送门:2018 ACM 国际大学生程序设计竞赛上海大都会赛 2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛2018-08-05 12:00:00 至 2018-08-05 17:00:0 ...
-
2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 J Beautiful Numbers (数位dp)
题目链接:https://ac.nowcoder.com/acm/contest/163/J 题目大意:给定一个数N,求区间[1,N]中满足可以整除它各个数位之和的数的个数.(1 ≤ N ≤ 1012 ...
-
2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 A,D
A链接:https://www.nowcoder.com/acm/contest/163/A Fruit Ninja is a juicy action game enjoyed by million ...
-
2018 ACM 国际大学生程序设计竞赛上海大都会 F - Color it (扫描线)
题意:一个N*M的矩形,每个点初始都是白色的,有Q次操作,每次操作将以(x,y)为圆心,r为半径的区域涂成黑点.求最后剩余白色点数. 分析:对每行,将Q次操作在该行的涂色视作一段区间,那么该行最后的白 ...
-
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 ...
-
2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛-K-Matrix Multiplication(矩阵乘法)
题目描述 In mathematics, matrix multiplication or matrix product is a binary operation that produces a m ...
随机推荐
-
用php生成一个excel文件(原理)
1.我们用php来生成一个excel文档来讲述其原理: excel2007里面的文档目录组成部分为: 2.我们使用ZipArchive()方法来生成一个简易的excel文件. 使用方法: 3.代码如下 ...
-
Eclipse *版本
关于Eclipse的版本介绍, Eclipse Standard 该版本是eclipse最基础的版本,适合Java se个人开发者.或希望根据自己需求配置插件的开发者使用. Eclipse IDE f ...
-
Lucas的数论(math)
Lucas的数论(math) 题目描述 去年的今日,Lucas仍然是一个热爱数学的孩子.(现在已经变成业界毒瘤了> <) 在整理以前的试题时,他发现了这么一道题目:求\(\sum\limi ...
-
ASP.NET MVC学习系列 WebAPI初探
转自http://www.cnblogs.com/babycool/p/3922738.html 一.无参数Get请求 一般的get请求我们可以使用jquery提供的$.get() 或者$.ajax( ...
-
Citrix 服务器虚拟化之六 Xenserver虚拟机创建与快照
Citrix 服务器虚拟化之六 Xenserver虚拟机创建与快照 在Xenserver上可以创建Windows和Linux等虚拟机,Xenserver支持大部分的主流操作系统,可以使用 XenCe ...
-
LwIP Application Developers Manual5---高层协议之DHCP,AUTOIP,SNMP,PPP
1.前言 本文主要讲述高层协议,包括DHCP 2.DHCP 2.1 从应用的角度看DHCP 你必须确保在编译和链接时使能DHCP,可通过在文件lwipopts.h里面定义LWIP_DHCP选项,该选项 ...
-
人生苦短之学习Python50本书籍(包涵基础、算法、机器学习、模块、爬虫框架、树莓派等)总有你想要的书籍
很多小伙伴说想学习想学习但是没有学习书籍,我给大家分享一大波学习书籍,具体的可以自己往下翻 <"笨办法学"Python3> Zed Shaw 著 (2018年5月) ...
-
redis 写磁盘出错 Can’t save in background: fork: Cannot allocate memory (转)
查看 Redis 日志 发现系统在频繁报错: [26641] 18 Dec 04:02:14 * 1 changes in 900 seconds. Saving… [26641] 18 Dec 04 ...
-
fcntl函数用法详解
功能描述:根据文件描述词来操作文件的特性. #include <unistd.h> #include <fcntl.h> int fcntl(int fd, int cmd) ...
-
对于ntp.conf的理解
允许与我们的时间源同步时间,但是不允许源查询或修改这个系统上的服务. # Permit time synchronization with our time source, but do not # ...