Considering three different lines, we can notice that they form a triangle if and only if their slopes are mutually different. The lines ~i~ and ~j~ have different slopes if ~A_i / B_i~ is different than ~A_j / B_j~ (be careful with division by zero). This leads us to our first solution with the complexity of ~\mathcal O(N^3)~, where we test whether the slopes are different for every line triplet ~(i, j, k)~.

If we could find out how many lines there are with a slope different than the slope of a certain pair of lines, the task could be solved by fixating all possible pairs of lines ~(i, j)~ with different slopes and add the answer to the query for lines ~i~ and ~j~ to the solution.

Let ~equal(x)~ represent the number of lines with a slope equal to the slope of line ~x~. Then the number of lines with a slope different than the slope of lines ~i~ and ~j~ is ~N-equal(i)-equal(j)~. The values of ~equal(x)~ can be preprocessed in the complexity of ~\mathcal O(N \log N)~ with simple sorting, which brings us to the solution of complexity ~\mathcal O(N^2)~.

For a solution valid for ~100\%~ of points, introduce two new functions: ~greater(x)~ and ~smaller(x)~ which tell us how many lines there are with slopes strictly greater or strictly smaller than the slope of line ~x~. These functions can also be easily preprocessed in the complexity of ~\mathcal O(N \log N)~ with the help of sorting. The number of triangles where the line ~i~ belongs and has the middle slope size can be calculated as ~greater(i) \times smaller(i)~. For the final solution, we only need to sum these values for each ~i~ from ~1~ to ~N~. The total complexity is ~\mathcal O(N \log N)~.