样例:

考试的时候没时间打了,随便敲了敲就交上去了,没想到竟然编译错误,忘定义n了23333

自己测了测能骗20分hhhh

考虑每个圆对答案的贡献,当一个圆被小圆内切的时候,分成了两半,对答案的贡献就是2。其余情况是1。

按左端点从小到大排序,左端点相同则按右端点由大到小。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 301000
int n;
struct haha{
	int l,r,o;
}cun[N];
int ans[N];
bool aaa(const haha &a,const haha &b){
	if(a.l==b.l)
	   return a.r>b.r;
	return a.l<b.l;
}
int cnt;
void dfs(int now){
	cnt=now+1;int maxr=cun[now].l;
	int flag=0;
	while(cnt<=n&&maxr<cun[now].r){
		if(cun[cnt].r>cun[now].r)
		  break;
		if(!flag&&cun[cnt].l==maxr){
			maxr=max(maxr,cun[cnt].r);
		}
		else
		  flag=1;
		dfs(cnt);
	}
	if(maxr==cun[now].r){
		ans[now]=2;
	}
	else
	  ans[now]=1;
}
int sum;
int main(){
	scanf("%d",&n);
	pos(i,1,n){
		int x,y;
		scanf("%d%d",&x,&y);
		cun[i].o=x;cun[i].l=x-y;cun[i].r=x+y;
	}
	sort(cun+1,cun+n+1,aaa);
	pos(i,1,n){
		if(!ans[i])
		  dfs(i);
		sum+=ans[i];
	}
	cout<<sum+1;
	return 0;
}

  

最新文章

  1. [django]windows下用Django,静态文件请求失败,出现UnicodeDecodeError
  2. SQL Server使用文件组备份降低备份文件占用的存储空间
  3. Canvas 教程
  4. Django学习笔记——安装(linux环境)
  5. PQ分区魔术师v9.0 中文版
  6. Ubuntu + Django + Nginx + uwsgi
  7. JavaScript(四)---- 函数
  8. 【多线程】-ThreadPool线程池
  9. 题解 P1496 【火烧赤壁】
  10. javascript基础 之 jQuery教程
  11. 测者的测试技术手册:自动的自动化框架EvoSuite集成Cobertura得到可视化的代码覆盖报告
  12. VSCode插件开发全攻略(二)HelloWord
  13. linux学习第十二天 (Linux就该这么学)找到一本不错的Linux电子书,附《Linux就该这么学》章节目录
  14. 【第196期】Drupal7 Features模块与 Drupal8 Configuration Management 模块对比
  15. github链接地址及
  16. springmvc返回中文乱码问题
  17. Qt实在太漂亮了
  18. LOADRUNNER重装经验
  19. 单线程和多线程处理1W条数据对比代码
  20. 关于BFS和dijkstra(2019.04.20)

热门文章

  1. [leetcode-599-Minimum Index Sum of Two Lists]
  2. MacTex XeLaTex xdvipdfmx:fatal: pdf_ref_obj(): passed invalid object. 报错的解决方法
  3. es6的一些知识点
  4. JavaWeb 后端 &lt;十四&gt; 文件上传下载
  5. 一颗简单的JDBC栗子
  6. 剥析surging的架构思想
  7. Centos7 安装keepalived实现高可用
  8. spring 页面跳转
  9. (转)Spring定时任务的几种实现
  10. Spring源码情操陶冶-AbstractApplicationContext#initApplicationEventMulticaster