Firecrackers scare Nian the monster, but they're wayyyyy too noisy! Maybe fireworks make a nice complement.

Little Tommy is watching a firework show. As circular shapes spread across the sky, a splendid view unfolds on the night of Lunar New Year's eve.

A wonder strikes Tommy. How many regions are formed by the circles on the sky? We consider the sky as a flat plane. A region is a connected part of the plane with positive area, whose bound consists of parts of bounds of the circles and is a curve or several curves without self-intersections, and that does not contain any curve other than its boundaries. Note that exactly one of the regions extends infinitely.


-----Input-----

The first line of input contains one integer n (1 ≤ n ≤ 3), denoting the number of circles.

The following n lines each contains three space-separated integers x, y and r ( - 10 ≤ x, y ≤ 10, 1 ≤ r ≤ 10), describing a circle whose center is (x, y) and the radius is r. No two circles have the same x, y and r at the same time.


-----Output-----

Print a single integer — the number of regions on the plane.


-----Examples-----
Input
3
0 0 1
2 0 1
4 0 1

Output
4

Input
3
0 0 2
3 0 2
6 0 2

Output
6

Input
3
0 0 2
2 0 2
1 1 2

Output
8



-----Note-----

For the first example, $000$ 

For the second example, [Image] 

For the third example, $\text{Q)}$

Difficulty: VERY_HARD
Tags: Geometry

Graph algorithms

Starter code:

Solutions:
from math import *
eps = 1e-09
ans = dict()
ans[0, 0, 0] = 4
ans[0, 0, 1] = 4
ans[0, 1, 0] = 4
ans[1, 0, 0] = 4
ans[0, 1, 1] = 4
ans[1, 0, 1] = 4
ans[1, 1, 0] = 4
ans[1, 1, 1] = 5
ans[0, 0, 2] = 5
ans[0, 2, 0] = 5
ans[2, 0, 0] = 5
ans[0, 1, 2] = 5
ans[0, 2, 1] = 5
ans[1, 0, 2] = 5
ans[1, 2, 0] = 5
ans[2, 0, 1] = 5
ans[2, 1, 0] = 5
ans[1, 1, 2] = 6
ans[1, 2, 1] = 6
ans[2, 1, 1] = 6
ans[0, 2, 2] = 6
ans[2, 0, 2] = 6
ans[2, 2, 0] = 6
ans[1, 2, 2] = 7
ans[2, 1, 2] = 7
ans[2, 2, 1] = 7
ans[2, 2, 2] = 8

def dist(A, B):
	return ((A[0] - B[0]) ** 2 + (A[1] - B[1]) ** 2) ** 0.5

def equal(A, B):
	return dist(A, B) < eps

def belong(P, i):
	return abs(dist(P, (c[i][0], c[i][1])) - c[i][2]) < eps

def intersection(c1, c2):
	O1 = (c1[0], c1[1])
	O2 = (c2[0], c2[1])
	(r1, r2) = (c1[2], c2[2])
	OO = (O2[0] - O1[0], O2[1] - O1[1])
	d = dist(O1, O2)
	if d > r1 + r2 or d < abs(r1 - r2):
		return []
	alp = atan2(OO[1], OO[0])
	phi = acos((r1 ** 2 + d ** 2 - r2 ** 2) / (2 * r1 * d))
	P1 = (r1 * cos(alp + phi) + O1[0], r1 * sin(alp + phi) + O1[1])
	P2 = (r1 * cos(alp - phi) + O1[0], r1 * sin(alp - phi) + O1[1])
	if equal(P1, P2):
		return [P1]
	return [P1, P2]

def solve():
	if n == 1:
		return 2
	if n == 2:
		res = 3
		inter = intersection(c[0], c[1])
		if len(inter) == 2:
			res += 1
		return res
	cnt = 0
	inter = [0, 0, 0]
	p = []
	for i in range(3):
		for j in range(i + 1, 3):
			cur = intersection(c[i], c[j])
			for P in cur:
				p.append(P)
				inter[i + j - 1] += 1
	for P in p:
		flag = 1
		for i in range(3):
			if not belong(P, i):
				flag = 0
		if flag:
			cnt += 1
	res = ans[tuple(inter)] - cnt // 3
	return res
n = int(input())
c = [tuple(map(int, input().split())) for i in range(n)]
print(solve())


from decimal import *
getcontext().prec = 40
eps = Decimal('1e-10')

class Circle:

	def __init__(self, x, y, r):
		self.x = x
		self.y = y
		self.r = r

	def contains(self, c):
		dd = (self.x - c.x) ** 2 + (self.y - c.y) ** 2
		return dd < (self.r - c.r) ** 2 and self.r > c.r

	def in_touches(self, c):
		dd = (self.x - c.x) ** 2 + (self.y - c.y) ** 2
		return dd == (self.r - c.r) ** 2 and self.r > c.r

	def ex_touches(self, c):
		dd = (self.x - c.x) ** 2 + (self.y - c.y) ** 2
		return dd == (self.r + c.r) ** 2

	def intersects(self, c):
		dd = (self.x - c.x) ** 2 + (self.y - c.y) ** 2
		return (self.r - c.r) ** 2 < dd < (self.r + c.r) ** 2

	def not_intersects(self, c):
		dd = (self.x - c.x) ** 2 + (self.y - c.y) ** 2
		return dd > (self.r + c.r) ** 2

	def get_intersections(self, c):
		(x1, y1, r1, x2, y2, r2) = map(Decimal, [self.x, self.y, self.r, c.x, c.y, c.r])
		RR = (x1 - x2) ** 2 + (y1 - y2) ** 2
		rx1 = (x1 + x2) / 2 + (r1 ** 2 - r2 ** 2) / (2 * RR) * (x2 - x1) + (2 * (r1 ** 2 + r2 ** 2) / RR - (r1 ** 2 - r2 ** 2) ** 2 / RR ** 2 - 1).sqrt() / 2 * (y2 - y1)
		ry1 = (y1 + y2) / 2 + (r1 ** 2 - r2 ** 2) / (2 * RR) * (y2 - y1) + (2 * (r1 ** 2 + r2 ** 2) / RR - (r1 ** 2 - r2 ** 2) ** 2 / RR ** 2 - 1).sqrt() / 2 * (x1 - x2)
		rx2 = (x1 + x2) / 2 + (r1 ** 2 - r2 ** 2) / (2 * RR) * (x2 - x1) - (2 * (r1 ** 2 + r2 ** 2) / RR - (r1 ** 2 - r2 ** 2) ** 2 / RR ** 2 - 1).sqrt() / 2 * (y2 - y1)
		ry2 = (y1 + y2) / 2 + (r1 ** 2 - r2 ** 2) / (2 * RR) * (y2 - y1) - (2 * (r1 ** 2 + r2 ** 2) / RR - (r1 ** 2 - r2 ** 2) ** 2 / RR ** 2 - 1).sqrt() / 2 * (x1 - x2)
		return {(rx1, ry1), (rx2, ry2)}

	def is_on(self, p):
		return abs((self.x - p[0]) ** 2 + (self.y - p[1]) ** 2 - self.r ** 2) < eps

	def __repr__(self):
		return '(%s, %s, %s)' % (self.x, self.y, self.r)

def count_regions(n, circles):
	if n == 1:
		return 2
	if n == 2:
		return 3 + circles[0].intersects(circles[1])
	if n == 3:
		(c0, c1, c2) = circles
		if c0.not_intersects(c1):
			if c0.intersects(c2):
				return 5 + c1.intersects(c2)
			elif c0.ex_touches(c2) or c2.not_intersects(c0):
				return 4 + c1.intersects(c2)
			elif c0.contains(c2) or c0.in_touches(c2):
				return 4
		elif c0.contains(c1):
			if c0.in_touches(c2) or c0.contains(c2):
				return 4 + c1.intersects(c2)
			elif c0.ex_touches(c2) or c0.not_intersects(c2):
				return 4
			elif c0.intersects(c2):
				return 5 + c1.intersects(c2)
		elif c0.in_touches(c1):
			if c0.in_touches(c2):
				if c1.intersects(c2):
					return 6
				elif c1.ex_touches(c2):
					return 5
				else:
					return 4
			elif c0.not_intersects(c2) or c0.ex_touches(c2):
				return 4
			elif c0.contains(c2):
				return 4 + c1.intersects(c2)
			elif c0.intersects(c2):
				if c1.intersects(c2):
					c0_x_c2 = c0.get_intersections(c2)
					return 6 + all((not c1.is_on(p) for p in c0_x_c2))
				else:
					return 5 + (c1.ex_touches(c2) or c2.in_touches(c1))
		elif c0.ex_touches(c1):
			if c0.in_touches(c2) or c0.contains(c2):
				return 4
			elif c0.ex_touches(c2):
				if c1.intersects(c2):
					return 6
				elif c1.ex_touches(c2):
					return 5
				else:
					return 4
			elif c0.not_intersects(c2):
				return 4 + c1.intersects(c2)
			elif c0.intersects(c2):
				if c1.intersects(c2):
					c0_x_c1 = c0.get_intersections(c1)
					return 7 + all((not c2.is_on(p) for p in c0_x_c1))
				elif c1.ex_touches(c2):
					return 6
				else:
					return 5
		elif c0.intersects(c1):
			if c0.not_intersects(c2):
				return 5 + c1.intersects(c2)
			elif c0.contains(c2):
				return 5 + c1.intersects(c2)
			elif c0.in_touches(c2) or c0.ex_touches(c2):
				if c1.intersects(c2):
					c0_x_c2 = c0.get_intersections(c2)
					return 6 + all((not c1.is_on(p) for p in c0_x_c2))
				else:
					return 5 + (c1.in_touches(c2) or c1.ex_touches(c2))
			elif c0.intersects(c2):
				c0_x_c1 = c0.get_intersections(c1)
				if c1.intersects(c2):
					if all((not c2.is_on(p) for p in c0_x_c1)):
						return 8
					elif all((c2.is_on(p) for p in c0_x_c1)):
						return 6
					else:
						return 7
				elif c1.in_touches(c2) or c1.ex_touches(c2) or c2.in_touches(c1):
					return 7 - any((c2.is_on(p) for p in c0_x_c1))
				else:
					return 6
		return 4
	return 0

def main():
	n = int(input())
	circles = [tuple(map(int, input().split())) for c in range(n)]
	circles.sort(key=lambda c: (-c[2], c[0], c[1]))
	circles = [Circle(*u) for u in circles]
	print(count_regions(n, circles))
main()


from math import sqrt
pt = lambda *a, **k: print(*a, **k, flush=True)
rd = lambda : map(int, input().split())
n = int(input())

def f(x1, y1, r1, x2, y2, r2):
	a = (r1 + r2) ** 2
	b = (r1 - r2) ** 2
	d = (x1 - x2) ** 2 + (y1 - y2) ** 2
	if d > a:
		return 1
	elif d == a:
		return 4
	elif d < b:
		return 3
	elif d == b:
		return 5
	else:
		return 2

def g(x1, y1, r1, x2, y2, r2):
	ds = (x1 - x2) ** 2 + (y1 - y2) ** 2
	d = sqrt(ds)
	A = (r1 ** 2 - r2 ** 2 + ds) / (2 * d)
	h = sqrt(r1 ** 2 - A ** 2)
	x = x1 + A * (x2 - x1) / d
	y = y1 + A * (y2 - y1) / d
	x3 = x - h * (y2 - y1) / d
	y3 = y + h * (x2 - x1) / d
	x4 = x + h * (y2 - y1) / d
	y4 = y - h * (x2 - x1) / d
	return (x3, y3, x4, y4)
if n is 1:
	pt(2)
if n is 2:
	(x1, y1, r1) = rd()
	(x2, y2, r2) = rd()
	a = f(x1, y1, r1, x2, y2, r2)
	pt(4 if a is 2 else 3)
if n is 3:
	(x1, y1, r1) = rd()
	(x2, y2, r2) = rd()
	(x3, y3, r3) = rd()
	a = f(x1, y1, r1, x2, y2, r2)
	b = f(x1, y1, r1, x3, y3, r3)
	c = f(x3, y3, r3, x2, y2, r2)
	t = [a, b, c]
	t.sort()
	(a, b, c) = t
	if a is 1 and b is 1 and (c in [1, 3, 4, 5]):
		pt(4)
	if a is 1 and b is 1 and (c is 2):
		pt(5)
	if a is 1 and b is 2 and (c is 2):
		pt(6)
	if a is 1 and b is 2 and (c in [3, 4, 5]):
		pt(5)
	if a is 1 and b in [3, 4, 5]:
		pt(4)
	if a is 2 and b is 2 and (c is 2):
		(x4, y4, x5, y5) = g(x1, y1, r1, x2, y2, r2)
		r = 8
		if abs((x4 - x3) ** 2 + (y4 - y3) ** 2 - r3 ** 2) < 1e-06:
			r -= 1
		if abs((x5 - x3) ** 2 + (y5 - y3) ** 2 - r3 ** 2) < 1e-06:
			r -= 1
		pt(r)
	if a is 2 and b is 2 and (c is 3):
		pt(6)
	if a is 2 and b is 2 and (c in [4, 5]):
		(x4, y4, x5, y5) = g(x1, y1, r1, x2, y2, r2)
		if abs((x4 - x3) ** 2 + (y4 - y3) ** 2 - r3 ** 2) < 1e-06 or abs((x5 - x3) ** 2 + (y5 - y3) ** 2 - r3 ** 2) < 1e-06:
			pt(6)
		else:
			pt(7)
	if a is 2 and b is 3:
		pt(5)
	if a is 2 and b in [4, 5]:
		pt(6)
	if a is 3 and b in [3, 4, 5]:
		pt(4)
	if a is 4 and b is 4 and (c is 4):
		pt(5)
	if a is 4 and b is 4 and (c is 5):
		pt(4)
	if a is 4 and b is 5 and (c is 5):
		pt(5)
	if a is 5 and b is 5 and (c is 5):
		pt(4)


from math import sqrt

class vector:

	def __init__(self, _x=0, _y=0):
		self.x = _x
		self.y = _y

	def len(self):
		return sqrt(self.x ** 2 + self.y ** 2)

	def len_sq(self):
		return self.x ** 2 + self.y ** 2

	def __mul__(self, other):
		if type(self) == type(other):
			return self.x * other.x + self.y * other.y
		return vector(self.x * other, self.y * other)

	def __mod__(self, other):
		return self.x * other.y - self.y * other.x

	def normed(self):
		length = self.len()
		return vector(self.x / length, self.y / length)

	def normate(self):
		self = self.normed()

	def __str__(self):
		return '(' + str(self.x) + ', ' + str(self.y) + ')'

	def __add__(self, other):
		return vector(self.x + other.x, self.y + other.y)

	def __sub__(self, other):
		return vector(self.x - other.x, self.y - other.y)

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

	def rot(self):
		return vector(self.y, -self.x)

class line:

	def __init__(self, a=0, b=0, c=0):
		self.a = a
		self.b = b
		self.c = c

	def intersect(self, other):
		d = self.a * other.b - self.b * other.a
		dx = self.c * other.b - self.b * other.c
		dy = self.a * other.c - self.c * other.a
		return vector(dx / d, dy / d)

	def fake(self, other):
		d = self.a * other.b - self.b * other.a
		return d

	def __str__(self):
		return str(self.a) + '*x + ' + str(self.b) + '*y = ' + str(self.c)

def line_pt(A, B):
	d = (A - B).rot()
	return line(d.x, d.y, d * A)

class circle:

	def __init__(self, O=vector(0, 0), r=0):
		self.O = O
		self.r = r

	def intersect(self, other):
		O1 = self.O
		O2 = other.O
		r1 = self.r
		r2 = other.r
		if O1 == O2:
			return []
		if (O1 - O2).len_sq() > r1 ** 2 + r2 ** 2 + 2 * r1 * r2:
			return []
		rad_line = line(2 * (O2.x - O1.x), 2 * (O2.y - O1.y), r1 ** 2 - O1.len_sq() - r2 ** 2 + O2.len_sq())
		central = line_pt(O1, O2)
		M = rad_line.intersect(central)
		if (O1 - O2).len_sq() == r1 ** 2 + r2 ** 2 + 2 * r1 * r2:
			return [M]
		d = (O2 - O1).normed().rot()
		if r1 ** 2 - (O1 - M).len_sq() < 0:
			return []
		d = d * sqrt(r1 ** 2 - (O1 - M).len_sq())
		return [M + d, M - d]

	def fake(self, other):
		O1 = self.O
		O2 = other.O
		r1 = self.r
		r2 = other.r
		if O1 == O2:
			return 1
		if (O1 - O2).len_sq() > r1 ** 2 + r2 ** 2 + 2 * r1 * r2:
			return 1
		rad_line = line(2 * (O2.x - O1.x), 2 * (O2.y - O1.y), r1 ** 2 - O1.len_sq() - r2 ** 2 + O2.len_sq())
		central = line_pt(O1, O2)
		return rad_line.fake(central)
n = int(input())
arr = []
m = 1
for i in range(n):
	(x, y, r) = map(int, input().split())
	arr.append(circle(vector(x, y), r))
for i in range(n):
	for j in range(i + 1, n):
		m *= arr[i].fake(arr[j])
for i in range(n):
	arr[i].O = arr[i].O * m
	arr[i].r = arr[i].r * m
s = set()
V = 0
for i in range(n):
	for j in range(i + 1, n):
		tmp = arr[i].intersect(arr[j])
		for e in tmp:
			s.add((round(e.x, 6), round(e.y, 6)))
V += len(s)
E = 0
par = [i for i in range(n)]

def get_par(v):
	if par[v] != v:
		par[v] = get_par(par[v])
	return par[v]

def unite(v, u):
	par[get_par(v)] = get_par(u)
for i in range(n):
	s = set()
	for j in range(n):
		tmp = arr[i].intersect(arr[j])
		if len(tmp):
			unite(i, j)
		for e in tmp:
			s.add((round(e.x), round(e.y)))
	E += len(s)
print(E - V + 1 + len({get_par(i) for i in range(n)}))