The crowdedness of the discotheque would never stop our friends from having fun, but a bit more spaciousness won't hurt, will it?

The discotheque can be seen as an infinite xy-plane, in which there are a total of n dancers. Once someone starts moving around, they will move only inside their own movement range, which is a circular area C_{i} described by a center (x_{i}, y_{i}) and a radius r_{i}. No two ranges' borders have more than one common point, that is for every pair (i, j) (1 ≤ i < j ≤ n) either ranges C_{i} and C_{j} are disjoint, or one of them is a subset of the other. Note that it's possible that two ranges' borders share a single common point, but no two dancers have exactly the same ranges.

Tsukihi, being one of them, defines the spaciousness to be the area covered by an odd number of movement ranges of dancers who are moving. An example is shown below, with shaded regions representing the spaciousness if everyone moves at the same time. [Image] 

But no one keeps moving for the whole night after all, so the whole night's time is divided into two halves — before midnight and after midnight. Every dancer moves around in one half, while sitting down with friends in the other. The spaciousness of two halves are calculated separately and their sum should, of course, be as large as possible. The following figure shows an optimal solution to the example above. [Image] 

By different plans of who dances in the first half and who does in the other, different sums of spaciousness over two halves are achieved. You are to find the largest achievable value of this sum.


-----Input-----

The first line of input contains a positive integer n (1 ≤ n ≤ 1 000) — the number of dancers.

The following n lines each describes a dancer: the i-th line among them contains three space-separated integers x_{i}, y_{i} and r_{i} ( - 10^6 ≤ x_{i}, y_{i} ≤ 10^6, 1 ≤ r_{i} ≤ 10^6), describing a circular movement range centered at (x_{i}, y_{i}) with radius r_{i}.


-----Output-----

Output one decimal number — the largest achievable sum of spaciousness over two halves of the night.

The output is considered correct if it has a relative or absolute error of at most 10^{ - 9}. Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-9}$.


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

Output
138.23007676

Input
8
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8

Output
289.02652413



-----Note-----

The first sample corresponds to the illustrations in the legend.

Difficulty: HARD
Tags: Graph traversal

Geometry

Greedy algorithms

Tree algorithms

Dynamic programming
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
from collections import namedtuple
from math import hypot, pi

def contains(fst, scd):
	return hypot(fst.x - scd.x, fst.y - scd.y) < fst.r

def area(circle):
	return pi * circle.r ** 2

def find_prev(side, circle):
	for prev in reversed(side):
		if contains(prev, circle):
			return prev
Circle = namedtuple('Circle', 'x y r')
n = int(input())
cs = []
for i in range(n):
	cs.append(Circle(*map(int, input().split())))
cs = sorted(cs, key=lambda circle: -circle.r)
ans = 0.0
counts = dict()
left = []
right = []
for (ind, cur) in enumerate(cs):
	prev_left = find_prev(left, cur)
	prev_right = find_prev(right, cur)
	if prev_left is None:
		left.append(cur)
		counts[cur] = True
		ans += area(cur)
	elif prev_right is None:
		right.append(cur)
		counts[cur] = True
		ans += area(cur)
	elif counts[prev_left]:
		left.append(cur)
		counts[cur] = False
		ans -= area(cur)
	else:
		left.append(cur)
		counts[cur] = True
		ans += area(cur)
print(ans)


from sys import stdin, stdout
import math

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

def inside(a, b):
	if dist(b, a) < a[2]:
		return True
	else:
		return False
n = int(stdin.readline().rstrip())
pointList = []
for _ in range(n):
	(x, y, r) = list(map(int, stdin.readline().rstrip().split()))
	pointList.append((x, y, r))
pointList.sort(key=lambda x: x[2], reverse=True)
positiveCounter = [0] * n
group = [0] * n
parent = [-1] * n
spaciousness = 0
for i in range(n):
	contained = -1
	for j in range(i - 1, -1, -1):
		if inside(pointList[j], pointList[i]):
			contained = j
			break
	if contained < 0:
		positiveCounter[i] = 1
		group[i] = 1
		spaciousness += math.pi * pointList[i][2] * pointList[i][2]
	else:
		parent[i] = j
		group[i] = 3 - group[j]
		if parent[j] >= 0:
			positiveCounter[i] = positiveCounter[j] * -1
			spaciousness += math.pi * pointList[i][2] * pointList[i][2] * positiveCounter[i]
		else:
			positiveCounter[i] = 1
			spaciousness += math.pi * pointList[i][2] * pointList[i][2] * positiveCounter[i]
print(spaciousness)


n = int(input())
d = [1] * n
p = [[] for i in range(n)]

def f():
	(x, y, r) = map(int, input().split())
	return (r * r, x, y)
t = sorted((f() for i in range(n)))
for i in range(n):
	(r, x, y) = t[i]
	for j in range(i + 1, n):
		(s, a, b) = t[j]
		if (a - x) ** 2 + (b - y) ** 2 < s:
			p[j].append(i)
			d[i] = 0
			break

def f(i):
	s = t[i][0]
	q = [(1, j) for j in p[i]]
	while q:
		(d, i) = q.pop()
		s += d * t[i][0]
		q += [(-d, j) for j in p[i]]
	return s
print(3.1415926536 * sum((f(i) for i in range(n) if d[i])))


import sys
input = sys.stdin.buffer.readline
from math import pi
n = int(input())
circles = [list(map(int, input().split())) for i in range(n)]
circles.sort(key=lambda x: -x[2])
mx = 0
groups = []
pars = []
for i in range(n):
	(x, y, r) = circles[i]
	added = -1
	for j in range(len(groups)):
		(xg, yg, rg) = groups[j][0]
		mx_r = r + ((x - xg) ** 2 + (y - yg) ** 2) ** 0.5
		if rg - mx_r > -1:
			added = j
			break
	if added == -1:
		groups.append([[x, y, r]])
		pars.append([0])
	else:
		pars[added].append(0)
		for j in range(len(groups[added])):
			(xg, yg, rg) = groups[added][j]
			mx_r = r + ((x - xg) ** 2 + (y - yg) ** 2) ** 0.5
			if rg - mx_r > -1:
				pars[added][-1] += 1
		groups[added].append([x, y, r])
for i in range(len(groups)):
	top_circles = 0
	for j in range(len(groups[i])):
		if pars[i][j] <= 1:
			mx += pi * groups[i][j][2] ** 2
		else:
			mx += (-1 + 2 * (pars[i][j] % 2)) * pi * groups[i][j][2] ** 2
print(mx)


import sys
input = sys.stdin.readline
from collections import *
from math import pi

def contain(i, j):
	(xi, yi, ri) = xyr[i]
	(xj, yj, rj) = xyr[j]
	if ri < rj:
		return False
	d2 = (xi - xj) ** 2 + (yi - yj) ** 2
	return d2 <= (ri - rj) ** 2

def bfs(s):
	q = deque([s])
	dist[s] = 0
	while q:
		v = q.popleft()
		for nv in G[v]:
			if dist[nv] == -1:
				dist[nv] = dist[v] + 1
				q.append(nv)
	return dist
n = int(input())
xyr = [tuple(map(int, input().split())) for _ in range(n)]
ins = [0] * n
outs = defaultdict(list)
for i in range(n):
	for j in range(n):
		if i == j:
			continue
		if contain(i, j):
			ins[j] += 1
			outs[i].append(j)
q = deque([i for i in range(n) if ins[i] == 0])
G = [[] for _ in range(n)]
is_root = [True] * n
while q:
	v = q.popleft()
	for nv in outs[v]:
		ins[nv] -= 1
		if ins[nv] == 0:
			G[v].append(nv)
			is_root[nv] = False
			q.append(nv)
dist = [-1] * n
for i in range(n):
	if is_root[i]:
		bfs(i)
ans = 0
for i in range(n):
	r = xyr[i][2]
	if dist[i] == 0 or dist[i] % 2 == 1:
		ans += r ** 2
	else:
		ans -= r ** 2
print(ans * pi)


s = 0
t = [list(map(int, input().split())) for i in range(int(input()))]
f = lambda b: a[2] < b[2] and (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 <= (a[2] - b[2]) ** 2
for a in t:
	k = sum((f(b) for b in t))
	s += (-1, 1)[(k < 1) + k & 1] * a[2] ** 2
print(3.1415926536 * s)


import math
z = math.pi
n = input()
a = input()
for i in range(int(n) - 1):
	a += '\n' + input()
a = a.split('\n')
for i in range(len(a)):
	a[i] = a[i].split(' ')
	a[i] = list(map(int, a[i]))
for i in range(len(a)):
	for j in list(reversed(range(i + 1, len(a)))):
		if a[i][2] < a[j][2]:
			(a[i], a[j]) = (a[j], a[i])

def dis(x, y):
	return math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2)
b = []
for i in range(len(a)):
	b.append(a[i][2] ** 2)
	for j in list(reversed(range(i))):
		if dis(a[i], a[j]) < a[j][2]:
			a[i].append(j)
			break
c = []
for i in a:
	if len(i) == 3:
		c.append(1)
	else:
		c.append(c[i[3]] + 1)
k = 0
for i in range(len(c)):
	if c[i] == 1:
		k += b[i]
	elif c[i] % 2 == 0:
		k += b[i]
	else:
		k -= b[i]
print(k * z)


import math

class circ:

	def __init__(self, x, y, r):
		self.x = x * 1.0
		self.y = y * 1.0
		self.r = r * 1.0
n = 0
n = int(input())
vec = []
for i in range(n):
	st = input().split(' ')
	a = int(st[0])
	b = int(st[1])
	c = int(st[2])
	vec.append(circ(a, b, c))
gr = [[] for i in range(n)]
pad = [-1 for i in range(n)]
vis = [False for i in range(n)]
for i in range(n):
	for k in range(n):
		if i == k:
			continue
		dist = math.hypot(vec[i].x - vec[k].x, vec[i].y - vec[k].y)
		if dist < vec[k].r and vec[k].r > vec[i].r and (pad[i] < 0 or vec[k].r < vec[pad[i]].r):
			pad[i] = k
for i in range(n):
	if pad[i] < 0:
		continue
	gr[pad[i]].append(i)
st = []
ans = 0.0
for i in range(n):
	if pad[i] >= 0 or vis[i]:
		continue
	st.append((i, 0))
	while len(st) > 0:
		(node, level) = st.pop()
		vis[node] = True
		mult = -1.0
		if level == 0 or level % 2 == 1:
			mult = 1.0
		ans += mult * (vec[node].r * vec[node].r * math.pi)
		for next in gr[node]:
			st.append((next, level + 1))
print(ans)


import sys

def inside(a, b):
	return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 < (a[2] + b[2]) ** 2

def main():
	pi = 3.141592653589793
	n = int(sys.stdin.readline())
	a = []
	p = [-1] * n
	for i in range(n):
		(x, y, r) = map(int, sys.stdin.readline().split())
		a.append([x, y, r])
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if inside(a[i], a[j]):
				if a[i][2] < a[j][2]:
					if p[i] == -1:
						p[i] = j
					elif a[p[i]][2] > a[j][2]:
						p[i] = j
				elif p[j] == -1:
					p[j] = i
				elif a[p[j]][2] > a[i][2]:
					p[j] = i
	q = []
	for i in range(n):
		if p[i] == -1:
			q.append((i, True))
	s = len(q)
	ans = 0.0
	for i in range(s):
		(c, b) = q[i]
		for j in range(n):
			if p[j] == c:
				q.append((j, True))
		ans += pi * a[c][2] * a[c][2]
	q = q[s:]
	while len(q) != 0:
		(c, b) = q.pop()
		for j in range(n):
			if p[j] == c:
				q.append((j, not b))
		if b:
			ans += pi * a[c][2] * a[c][2]
		else:
			ans -= pi * a[c][2] * a[c][2]
	print(ans)
main()