eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Empty Triangles

Empty Triangles

\includegraphics{https://static.e-olymp.com/content/04/04380af3e94a419a8f48bd29abdddc985e9ec397.jpg} \includegraphics{https://static.e-olymp.com/content/93/9376771c0536c2daf8d811ec2b5015620c193f66.jpg} 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 \textbf{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 \textbf{4} straight lines, we can only make \textbf{2} empty triangles, whereas the total number of triangles can be as big as \textbf{4}. Refer to the diagram. In fact, a general formula for the maximum number of empty triangles that can be drawn with \textbf{N} lines is not known. The hard part, however, is to find the right configuration of the lines. Your job is much easier; given \textbf{N} straight lines on the plane, count the number of empty triangles. \InputFile The input consists of multiple test cases. Each test case begins with a line containing an integer \textbf{N}, \textbf{1} ≤ \textbf{N} ≤ \textbf{500}, which indicates the number of lines on the plane. The next \textbf{N} lines each contain four integers \textbf{x_1}, \textbf{y_1}, \textbf{x_2}, and \textbf{y_2} (between \textbf{−1000} and \textbf{1000}), representing a straight line that goes through (\textbf{x_1}, \textbf{y_1}) and (\textbf{x_2}, \textbf{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 \textbf{N = 0}. \textbf{Ouput} For each test case, print out a single line that contains the number of empty triangles formed by the given lines.
Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #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
Вихідні дані #1
2
0
Джерело 2011 Stanford Local ACM Programming Contest, Saturday, October 8th, 2011