月光的魔法
背景
影几欺哄了众生了
天以外——
月儿何曾圆缺
描述
有些东西就如同月光的魔法一般.
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
- 上传者