24716번 - Three Countries 스페셜 저지다국어

Today, you want to measure the accessible area of Teyvat.

Mondstadt, Liyue, and Inazuma are the three countries in Teyvat. The territories of these countries can be regarded as three circles $c_1$, $c_2$, and $c_3$, respectively. It is possible that some of the circles overlap.

Let $S_i$ be the set of points in $c_i$. The area of Teyvat, $S$, is defined as the convex hull of points in $S_1 \cup S_2 \cup S_3$.

Formally, $S$ is the smallest set of points satisfying the following two conditions:

• $S \supseteq S_1 \cup S_2 \cup S_3$,
• $\forall p_1, p_2 \in S, \forall \alpha \in [0, 1], \alpha p_1 + (1-\alpha)p_2 \in S$.

You are given the circles $c_1$, $c_2$, and $c_3$. Your task is to calculate the area of $S$.

The first line contains a single integer $t$, the number of test cases ($1 \leq t \leq 10^4$).

Each test case is given on three lines. The $i$-th of these lines contains three integers, $x$, $y$, and $r$, which are the coordinates of the center and the radius of $i$-th circle ($1 \leq x, y ,r \leq 100$).

For each test case, output a single real number representing the area of $S$. 

Your answer will be considered correct if its absolute or relative error when compared with the jury's answer is no more than $10^{-6}$.