题目描述

在二维笛卡尔平面上有 $n$ 个喷洒器，每个喷洒器可以浇灌一个圆形区域内的内部（含边界）。

你需要计算可以被这些喷洒器浇灌到的区域面积。

输入格式

第一行包含一个整数 $T$ ($1 \leq T \leq 10^4$)，表示测试用例的数量。

接下来是 $T$ 个测试用例。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$)，表示喷洒器的数量。

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i, y_i$ 和 $r_i$ ($-10^4 \leq x_i, y_i \leq 10^4, 1 \leq r_i \leq 10^4$)，表示第 $i$ 个喷洒器浇灌一个以 $(x_i, y_i)$ 为中心，半径为 $r_i$ 的圆形区域内或边界上的面积。

保证 $T$ 个测试用例中 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，在一行中输出一个实数，表示可以被这些喷洒器浇灌到的区域面积。

如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则将被视为正确。更正式地，假设你的输出为 $a$，标准答案为 $b$，当且仅当 $\frac{|a-b|}{\max(1, |b|)} \leq 10^{-6}$ 时，你的输出会被接受。

2
3
0 0 2
0 2 2
2 0 2
3
0 0 2
0 3 2
3 0 2

27.360855087873111763
34.072617811256640852

解释 #1

数据范围

额外挑战