Circles dividing the plane
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