Hide

Problem C
Counting Triangles

The following figure contains a lot of triangles, $88$ in fact. Two of them are highlighted. The figure is made up of 15 line segments. You have a triangle if you can start at an intersection of line segments $a$ and $b$, follow $b$ until it intersects with some line segment $c$ and then follow $c$ until it intersects with $a$.

\includegraphics[width=0.5\textwidth ]{triangles}

Counting triangles by hand can be a bit tedious, so you decide to write a simple program to help out.

Input

Input consists of up to $250$ test cases. Each test case starts with an integer $1 \le n \le 50$. This is followed by $n$ lines, each containing four space-separated real values, $x_1~ y_1~ x_2~ y_2$ which defines a line segment from from point $(x_1,y_1)$ to $(x_2,y_2)$. Within a test case, line segments may be parallel, but two segments never intersect at more than a single point. Also, no more than two line segments intersect at a single point. All real values are in the range $[0,100]$ and have at most $6$ digits after the decimal point. The end of all test cases is marked with a value of zero for $n$.

Output

For each test case, output the number of triangles defined by the given line segments.

Sample Input 1 Sample Output 1
5
1.350 1.890 3.825 3.330
3.915 1.575 2.385 3.690
1.350 2.295 4.545 1.845
2.250 1.710 4.140 3.060
2.250 3.150 3.465 1.755
9
4.050 2.115 6.660 3.825
6.705 3.330 4.455 5.760
5.355 5.940 2.205 4.320
2.475 5.355 3.375 2.205
2.070 2.970 5.985 2.205
4.905 1.710 5.760 5.670
6.300 2.790 3.150 5.670
2.250 3.510 6.705 4.545
2.430 4.140 6.345 2.970
0
4
11

Please log in to submit a solution to this problem

Log in