Time Limit: 2 sec / Memory Limit: 512 MB
Problem Statement
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.
Input
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
Output the common area of given triangles in a line. The output can contain an absolute or relative error no more than $10^{−6}$.
Sample Input 1
2 0 0 2 0 0 2 0 1 2 1 0 3
Output for Sample Input 1
0.5
Sample Input 2
2 0 0 100 0 50 100 50 -50 100 50 0 50
Output for Sample Input 2
3125
Sample Input 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
Output for Sample Input 3
0.5