printРабочее место участника

printЗадачи

2112. Circles

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Enjoying a casual afternoon walk in the coordinate system, little Luka has encountered `N` unique circles with its centers lying on the x-axis. The circles do not intersect, but they can touch (from the inside and the outside). Fascinated with circles, Luka wondered how many regions the circles divide the plane into. Of course, you are going to help him answer this question.
A region is a set of points such that each two points can be connected with a continuous curve, without cutting through any of the circles.
28755.png
One of the possible layouts of circles
The first line of input contains the integer `N` (`1\ ≤\ N\ ≤\ 300\ 000`), the number of circles.
Each of the following `N` lines contains two integers `x_i` and `r_i` (`-10^9\ \ ≤\ x_i\ ≤\ 10_9`, `1\ ≤\ r_i\ ≤\ 10^9`), the number `x_i` representing the `x` coordinate of the `i`th circle and the number `r_i` representing the radius of the `i`th circle.
All the circles in the input will be unique.
The first and only line of output must contain the required number from the task.

Sample Input #1

2
1 3
5 1

Sample Output #1

3

Sample Input #2

3
2 2
1 1
3 1

Sample Output #2

5

Sample Input #3

4
7 5
-9 11
11 9
0 20

Sample Output #3

6
Clarification of the third example: The example corresponds to the image in the task statement.
Source: COCI 2013/2014, contest #6
loading