F. Union of Circular Sectors
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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.
Output

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}$$$.

Examples
Input
3
0 0 5 0 -5 0
-1 -1 4 3 -6 3
1 -2 2 -2 1 -1
Output
47.9378026054
Input
1
0 0 -10000 -10000 10000 10000
Output
314159265.3589793238
Note

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