Empty Triangles

It is surprisingly easy to turn a very simple question into a brutally hard one. Here is an example.

How many triangles can you form with $N$ lines in the plane? If the lines have pairwise different slopes and no three of them pass through a single point, they form $\binom{N}{3}$ triangles, which is the largest number possible.

That was not so hard. But now count only the empty triangles — those whose interior is not crossed by any of the lines. Suddenly the number becomes very small. For example, with $4$ lines you can form at most $2$ empty triangles, even though the total number of triangles can be as large as $4$ (see the figure).

No general formula is known for the maximum number of empty triangles that $N$ lines can form; the hard part is choosing the right arrangement of the lines. Your task is easier: given $N$ lines in the plane, count how many empty triangles they form.

Figure 1: Four lines forming two empty triangles (shaded).

The input consists of several test cases. Each test case begins with a line containing an integer $N$ ($1 \le N \le 500$), the number of lines. Each of the next $N$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$ (each between $-1000$ and $1000$), describing a line that passes through the points $(x_1, y_1)$ and $(x_2, y_2)$. No three lines meet at a single point, and all lines are distinct. The input ends with a line containing $N = 0$, which is not processed.

For each test case, print a single line containing the number of empty triangles formed by the given lines.