问题 5200 --圆的分割

5200: 圆的分割

题目描述

给定 $n$ 个圆,每个圆的圆心都在二维平面直角坐标系的 X 轴上,任意两个圆的交点不能超过一个(也就是说,它们可以相切,但不能相交)。 请问这些圆将这个二维平面分割成了多少个区域(连通的部分算同一个区域)?

输入

第一行:一个正整数 $n$; 接下来有 $n$ 行,每行两个整数 $x_i$ 和 $r_i$,$x_i$ 表示一个圆的圆心的X坐标,$r_i$ 表示该圆的半径。

输出

单个整数:表示答案。

样例输入输出

输入#1 复制
3
2 2
1 1
3 1 
输出#1 复制
5
输入#2 复制
4
7 5
-9 11
11 9
0 20 
输出#2 复制
6
输入#3 复制
2
1 3
5 1 
输出#3 复制
3

提示

+ 对于 $30\%$ 的数据,$n\leq 1000$; + 对于 $100\%$ 的数据,$n\leq 100000$,$-10^9\leq x_i\leq 10^9$,$1\leq r_i\leq 10^9$
序号 标题 作者 发表时间 费用 订购数 操作