/ Vijos / 题库 /

月光的魔法

月光的魔法

背景

影几欺哄了众生了
天以外——
月儿何曾圆缺

描述

有些东西就如同月光的魔法一般.

Luke是爱着vijos的.
他想为自己心爱的东西画些什么.

就画N个圆吧.
把它们的圆心都固定在x轴上.

圆与圆.
为了爱,两两不能相交.
为了爱,它们可以互相贴在一起.
内切或外切,都是允许的.

vijos的美丽,在于人心.
vijos的孩子们,一定能告诉大家:Luke画的圆究竟把平面分割成了多少块?

月光恬美地洒在大地上.
Luke知道,如果什么都不画,平面就只有一块.多美呢!
Luke知道,只画一个圆,平面就分成了两块.也很美呢!
但Luke还是要多画一些的,因为他真的深爱着vijos呢.

格式

输入格式

输入数据第一行:输出一个整数N,1<=N<=300,000.表示圆的个数.
之后N行,每一行有2个整数,x[i]和r[i]表示圆心固定在x[i]的位置,半径为r[i].
-1,000,000,000<=x[i]<=1,000,000,000
1<=r[i]<=1,000,000,000
所有圆都是唯一的,不会出现重叠.

输出格式

输出只有一行,要求输出平面被分割成了多少块.

样例1

样例输入1

2
1 3
5 1

样例输出1

3

样例2

样例输入2

3
2 2
1 1
3 1

样例输出2

5

样例3

样例输入3

4
7 5
-9 11
11 9
0 20

样例输出3

6

限制

对于40%的数据:
N<=5000.
对于100%的数据:
1<=N<=300,000;-1,000,000,000<=x[i]<=1,000,000,000;1<=r[i]<=1,000,000,000

信息

ID
1883
难度
7
分类
(无)
标签
(无)
递交数
844
已通过
134
通过率
16%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

国庆节模拟赛之繁星春水