【NOI考前欢乐赛】小奇画画

2016年6月26日1,6910
【题目背景】
红莲 清泪两行欲吐半点却无
如初 是你杳然若绯雾还在水榭畔

画楼处

是谁衣白衫如初

谁红裳如故

——《忆红莲》

【问题描述】

小奇想画几朵红莲,可惜它刚开始学画画,只能从画圆开始。小奇画了n个圆,它们的圆心都在x轴上,且两两不相交(可以相切)。现在小奇想知道,它画的圆把画纸分割成了多少块?(假设画纸无限大)

【输入格式】

第一行包括1个整数n。

接下来n行,每行两个整数x,r,表示小奇画了圆心在(x,0),半径为r的一个圆。

【输出格式】

输出一个整数表示答案。

【样例输入】

4

7 5

-9 11

11 9

0 20

【样例输出】

6

【数据范围】

对于30%数据,n<=5000;

对于100%数据,1<=n<=300000,-10^9<=x<=10^9,1<=r<=10^9。

题解

本题加强自vijos 月光的魔法 【NOIP模拟赛】天神下凡

zhber:

考虑圆对答案的贡献:当它并没有被沿着直径分开的时候,对答案的贡献是1。如果被分开贡献是2。所以按r从小到大排序,把树的左右端点离散,用一个线段树维护区间是否被覆盖。如果已经被覆盖,贡献是2,否则贡献是1

我的做法:

在一般情况n个圆划分出n+1个平面

对圆进行排序以后,用栈处理出每个圆的一级祖先形成一棵树

若一个结点的儿子的圆的直径与其相等,说明它的儿子首尾相接把它割成了两部分,多形成一个平面,这个直接搜索