题目描述

给定坐标平面上 $n$ 个圆。任意两个圆的边界至多只有一个公共点 —— 即它们必定相离或相切。

对于一个圆的集合，定义其 异或面积 为平面上被该集合中奇数个圆覆盖的图形面积。

现在需要将这 $n$ 个圆划分为两个集合，每个圆恰好在两个集合中的一个内。

请求出合法的划分方案中，两个集合分别计算的 异或面积 之和的最大值

输入格式

输入的第一行包含一个正整数 $n$ ( $1 \leq n \leq 1000$ ) —— 圆的数目。

接下来 $n$ 行，每行包含三个整数 $x_{i}$ , $y_{i}$ and $r_{i}$ ( $-10^{6}<=x_{i},y_{i}<=10^{6}$ , $1<=r_{i}<=10^{6}$ )—— 描述一个圆心位于 $(x_{i},y_{i})$ ,半径为 $r_{i}$ 的圆。

输出格式

输出一个十进制实数 —— 合法的划分方案中，两个集合异或面积 之和的最大值。

当选手答案与参考答案的相对误差或绝对误差不超过 $10^{-9}$ 时被视为正确。形式化地，若选手输出为 $a$ ，参考答案为 $b$，答案被视为正确当且仅当 $\frac{|a-b|}{\max{(1, |b|)}} \le 10^{-9}$。

样例 #1

样例输入 #1

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

样例输出 #1

138.23007676

样例 #2

样例输入 #2

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

样例输出 #2

289.02652413