시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Fallen angel Yohane plans to draw a magic symbol composed of triangles on the earth. By casting some magic spell on the symbol, she will obtain magic power; this is the purpose for which she will draw a magic symbol. The magic power yielded from the magic symbol is determined only by the common area of all the triangles. Suppose the earth is a two-dimensional plane and the vertices of the triangles are points on the plane. Yohane has already had a design of the magic symbol, i.e. the positions, sizes, shapes of the triangles. However, she does not know how much magic power will be obtained from the symbol. Your task as a familiar of the fallen angel is to write a program calculating the common area of given triangles on a two-dimensional plane.

입력

The input consists of a single test case in the following format.

$N$
$x_{1,1}$ $y_{1,1}$ $x_{1,2}$ $y_{1,2}$ $x_{1,3}$ $y_{1,3}$
...
$x_{N,1}$ $y_{N,1}$ $x_{N,2}$ $y_{N,2}$ $x_{N,3}$ $y_{N,3}$

The first line contains an integer $N$, which is the number of triangles ($1 \le N \le 10^5$). The $i$-th line of the following $N$ lines contains six integers $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, $y_{i,2}$, $x_{i,3}$, and $y_{i,3}$, where $(x_{i, j}, y_{i, j})$ is the coordinate of the $j$-th vertex of the $i$-th triangle ($-1{,}000 \le x_{i, j}, y_{i, j} \le 1{,}000$).

You can assume the followings:

  • Every triangle has a positive area.
  • The vertices of every triangle are in the counter-clockwise order.

출력

Output the common area of given triangles in a line. The output can contain an absolute or relative error no more than $10^{−6}$.

예제 입력 1

2
0 0 2 0 0 2
0 1 2 1 0 3

예제 출력 1

0.5

예제 입력 2

2
0 0 100 0 50 100
50 -50 100 50 0 50

예제 출력 2

3125

예제 입력 3

5
0 0 1 0 0 1
0 0 2 0 0 2
0 0 3 0 0 3
0 0 4 0 0 4
0 0 5 0 0 5

예제 출력 3

0.5