eolymp
bolt
Try our new interface for solving problems
Məsələlər

Empty Triangles

Empty Triangles

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Do you know how easy it is to make a very simple problem into a brutally hard one? Here is an example. How many triangles can you make with N straight lines in the plane? As long as they have different slopes and no three of them meet at a single point, there will be triangles, which is the maximum possible you can get.

Okay, that wasn’t too bad. But let’s see what happens if we only count triangles that are empty (that is, none of the lines pass through the interior of the triangle). Then, the number of triangles suddenly becomes very small. For example, with 4 straight lines, we can only make 2 empty triangles, whereas the total number of triangles can be as big as 4. Refer to the diagram.

In fact, a general formula for the maximum number of empty triangles that can be drawn with N lines is not known. The hard part, however, is to find the right configuration of the lines. Your job is much easier; given N straight lines on the plane, count the number of empty triangles.

Giriş verilənləri

The input consists of multiple test cases. Each test case begins with a line containing an integer N, 1N500, which indicates the number of lines on the plane. The next N lines each contain four integers x_1, y_1, x_2, and y_2 (between −1000 and 1000), representing a straight line that goes through (x_1, y_1) and (x_2, y_2). It is guaranteed that no three lines meet at the same point, and all the lines are distinct. The input terminates with a line with N = 0.

Ouput

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

Nümunə

Giriş verilənləri #1
4
0 0 1 2
0 0 -1 2
1 0 1 1
-1 0 -1 -1
5
0 0 1 0
0 1 1 1
0 2 1 2
0 3 1 3
0 4 1 4
0
Çıxış verilənləri #1
2
0
Mənbə 2011 Stanford Local ACM Programming Contest, Saturday, October 8th, 2011