JMU CS280 SP18 WK15

Start

2018-04-24 21:30 CEST

JMU CS280 SP18 WK15

End

2018-04-28 05:59 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -116 days 8:29:30

Time elapsed

80:29:00

Time remaining

0:00:00

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