410309: GYM104008 F Union of Circular Sectors

You are given $$$n$$$ non-degenerated circular sectors with the following guarantees:

• The central angle is less than or equal to 180 degrees.
• There are no two sectors with exactly the same radius and center.
• If two collinear radii belonging to two circular sectors exist, they won't share any point.

Please calculate the area of the union of those circular sectors.

The first line contains one integer $$$n$$$ ($$$1\le n\le 1000$$$), denoting the number of semicircles.

Then follows $$$n$$$ lines, the $$$i$$$-th line contains six integers $$$x_{i,o},\ y_{i,o},\ x_{i,a},\ y_{i,a},\ x_{i,b},\ y_{i,b}$$$ ($$$-10^4\le x_{i,o},\ y_{i,o},\ x_{i,a},\ y_{i,a},\ x_{i,b},\ y_{i,b}\le 10^4$$$), which denotes the coordinate of the center $$$O_i(x_{i,o},\ y_{i,o})$$$ and the two corners $$$A_i(x_{i,a},\ y_{i,a})$$$ and $$$B_i(x_{i,b},\ y_{i,b})$$$ of the $$$i$$$-th circular sector. The $$$i$$$-th sector is defined as the area that segment $$$O_iA_i$$$ passes through when it rotates counter-clockwise around the point $$$O_i$$$ to $$$O_iB_i$$$. It is guaranteed that:

• $$$O_i$$$, $$$A_i$$$ and $$$B_i$$$ won't coincide.
• $$$|O_iA_i|=|O_iB_i|$$$.
• $$$\overrightarrow{O_iA_i}\times \overrightarrow{O_iB_i}\ge 0$$$, where $$$\times$$$ denotes the modular of cross product of two 2-dimensional vectors, defined as $$$a \times b = a.x \cdot b.y - a.y \cdot b.x$$$. The equal sign is taken if and only if the two vectors are opposite.

Print the area of the union of those circular sectors by a single decimal number in a single line. Your answer will be accepted if the absolute or relative error to the jury's answer is less than or equal to $$$10^{-6}$$$.

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

47.9378026054

1
0 0 -10000 -10000 10000 10000

314159265.3589793238

The first test case can be illustrated in the following figure.