Circles dividing the plane Task

You will be given a set of circles in the plane with their centers on the line y=0. It is guaranteed that no pair of circles has more than one common point.

Your task is to determine into how many regions into which the circles divide the plane. A region is an inclusion-maximal contiguous set of points not intersecting any of the circles.

You should write a program that computes this answer when given a description of the circles.



Here's an example:



On the left side you see the circles drawn in the plane. However, in the right half of the picture, the regions produced by the circles are colored distinctly (one color per region). There are six regions in this example.



Input

The first line of the input contains a number, N, the number of circle descriptions to follow. This line is optional, if your solution works without it, it's fine.

The following N lines each contain two integers, xi and ri > 0, representing a circle with center (xi, 0) and radius ri.

It is guaranteed that no pair of circles has more than one common point. It is further guaranteed that xi and ri do not exceed 10^9 in absolute value (so they comfortably fit into a 32-bit integer).



The input may be:


read from STDIN
read from a file named I in the current directory


Alternatively, the input could be:


available as a string (including newlines) in a global variable
on the stack




Output

This should be a single integer, the number to regions produced. This should be written to STDOUT or a file named O in the current directory.



Rules


Shortest code in bytes wins
+200 byte penalty if your code does not have a runtime + space complexity polynomial in n
-100 byte bonus for worst-case expected runtime + space complexity O(n log n)
-50 byte bonus for worst-case expected runtime + space complexity O(n)
-100 byte bonus for deterministic runtime + space complexity O(n)


While assessing the runtime:


Assume that hash tables have O(1) expected runtime for insert, delete and lookup, regardless of the sequence of operations and the input data. This may or may not be true, depending on whether the implementation uses randomization.
Assume that the builtin sort of your programming language takes deterministic O(n log n) time, where n is the size of the input sequence.
Assume that arithmetic operations on input numbers take only O(1) time.
Do not assume that input numbers are bound by a constant, although, for practical reasons, they are. This means that algorithms like radix sort or counting sort are not linear time. In general, very large constant factors should be avoided.




Examples

Input:

2 
1 3
5 1


Output: 3



Input:

3
2 2
1 1
3 1


Output: 5

4
7 5
-9 11
11 9
0 20




Input:

9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2


Output: 11



Hints

We can use the following idea for a very compact solution. Lets intersect the set of circles with the X axis and interpret the intersection points as nodes in a planar graph:



Every circle produces exactly 2 edges in this graph and up to two nodes. We can count the number of nodes by using a hash table to keep track of the total number of distinct left or right borders.

Then we can use the Euler characteristic formula to compute the number of faces of a drawing of the graph:

V - E + F - C = 1

F = E - V + C + 1

To compute C, the number of connected components, we can use a depth-first search.



Note: This problem idea is borrowed from a recent Croatian programming contest, but please don't cheat by looking at the solution outlines. :)
Ruby - 312 306 285 273 269 259 characters

This answer has been superseded by my other approach which uses considerably less characters and runs in O(n log n).

Okay, let's go. For starters, I just wanted a working implementation, so this is not algorithmically optimised yet. I sort the circles from largest to smallest, and build a tree (circles included in other circles are children of those larger ones). Both operations take O(n^2) at worst and O(n log n) at best. Then I iterate through the tree to count areas. If the children of a circle fill up its entire diameter, there are two new areas, otherwise there is just one. This iteration take O(n). So I have overall complexity O(n^2) and qualify for neither reward nor penalty.

This code expects the input without the number of circles to be stored in a variable s:

t=[]
s.lines.map{|x|x,r=x.split.map &amp;:to_i;{d:2*r,l:x-r,c:[]}}.sort_by!{|c|-c[:d]}.map{|c|i=-1;n=t
while o=n[i+=1]
if 0&gt;d=c[:l]-o[:l]
break
elsif o[:d]&gt;d
n=o[:c]
i=-1
end
end
n[i,0]=c}
a=1
t.map &amp;(b=-&gt;n{d=0
n[:c].each{|c|d+=c[:d]}.map &amp;b
a+=d==n[:d]?2:1})
p a


Ungolfed version (expects input in variable string):

list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &amp;:to_i
  list&lt;&lt;{x:x, d:2*radius, l:x-radius, r:x+radius, children:[]}
}
list.sort_by! { |circle| -circle[:d] }
tree = []
list.map { |circle|
  i = -1
  node = tree
  while c=node[i+=1]
    if circle[:x]&lt;c[:l]
      break
    elsif circle[:x]&lt;c[:r]
      node = c[:children]
      i = -1
    end
  end
  node[i,0] = circle
}
areas = 1
tree.map &amp;(count = -&gt; node {
  d = 0
  i = -1
  while c=node[:children][i+=1]
    count.call c
    d += c[:d]
  end
  areas += d == node[:d] ? 2 : 1
})
p areas