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 &: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>d=c[:l]-o[:l]
break
elsif o[:d]>d
n=o[:c]
i=-1
end
end
n[i,0]=c}
a=1
t.map &(b=->n{d=0
n[:c].each{|c|d+=c[:d]}.map &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 &:to_i
  list<<{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]<c[:l]
      break
    elsif circle[:x]<c[:r]
      node = c[:children]
      i = -1
    end
  end
  node[i,0] = circle
}
areas = 1
tree.map &(count = -> 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

Ruby, 203 183 173 133 - 100 = 33 characters

So here is a different approach. This time, I sort the circles by their left-most point. Circles touching at their left-most point are sorted from largest to smallest. This takes O(n log n) (well, Ruby uses quick sort, so actually O(n^2) but implementing merge/heap sort is probably beyond the scope of this challenge). Then I iterate over this list, remembering all left-most and right-most positions of the circles I have visited. This allows me to detect if a series of circles connects all the way across an enclosing larger circle. In this case, there are two subareas, otherwise just one. This iteration takes only O(n) giving a total complexity of O(n log n) which qualifies for the 100 character reward.

This snippet expects the input to be supplied via a file in the command-line arguments without the number of circles:

l,r={},{}
a=1
$<.map{|x|c,q=x.split.map &:to_r;[c-q,-2*q]}.sort.map{|x,y|a+=r[y=x-y]&&l[x]?2:1
l[y]=1 if l[x]&&!r[y]
l[x]=r[y]=1}
p a

Ungolfed version (expects input in a variable string):

list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_r
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius}
}
list.sort_by! { |circle| circle[:l] + 1/circle[:d] }
l,r={},{}
areas = 1
list.map { |circle|
  x,y=circle[:l],circle[:r]
  if l[x] && r[y]
    areas += 2
  else
    areas += 1
    l[y]=1 if l[x]
  end
  r[y]=1
  l[x]=1
}
p areas

Mathematica, 125 122 - 150 = -28 chars

I don't know the complexity of the built-in function ConnectedComponents.

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&

Usage:

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&[
"9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2"]

11