시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB6214818.182%

문제

На плоскости задано $n$ кругов. У кругов могут быть общие точки, но любые два круга либо не имеют общих точек, либо имеют одну общую точку, либо один круг вкладывается в другой.

Найдите площадь объединения всех заданных кругов.

입력

Первая строка входного файла содержит число $n$ ($1 \le n \le 100\,000$). Следующие $n$ строк содержат по три целых числа. Описание $i$-го круга состоит из трех целых чисел: координат центра $x_i$ и $y_i$, а также его радиуса $r_i$ ($-10^6\le x_i, y_i \le 10^6$, $1 \le r_i \le 10^6$).

출력

Выведите единственное вещественное число --- площадь объединения всех заданных кругов. Ваш ответ должен иметь абсолютную или относительную погрешность не больше $10^{-9}$.

예제 입력 1

4
2 2 2
2 2 1
5 2 1
5 5 2

예제 출력 1

28.2743338823081391