Problem L. Lines and triangles ≡

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Let's consider a configuration of n lines on a plane. The task is to count the maximum number of triangle cells formed as a result of subdivison plane by these lines.

Input format

The input begins with a natural number n, followed by exactly n lines. Each line is defined by a pair of distinct points: (Axi, Ayi), (Bxi, Byi).

Output format

The output should contain the number of triangles obtained.

Constraints

It is guaranteed that no two lines coincide.

All input values are integers.

 − 104 ≤ (Axi, Ayi, Bxi, Byi) ≤ 104, 3 ≤ n ≤ 300

Sample tests

No. Standard input Standard output
1 
5
  0 -20  15 -20
-10  10  35 -35
  0   0   0 -10
-10   0  30   0
-20   0   0  20
 
3
2 
5
-10   0   0 -20
-20 -10 -10 -30
  0   0  10  24
  0  10  10 -10
-10   0   0  24

0
0.066s 0.010s 15