Editorial for COCI '13 Contest 5 #5 Trokuti
Submitting an official solution before solving the problem yourself is a bannable offence.
Considering three different lines, we can notice that they form a triangle if and only if their slopes are mutually different. The lines and
have different slopes if
is different than
(be careful with division by zero). This leads us to our first solution with the complexity of
, where we test whether the slopes are different for every line triplet
.
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 with different slopes and add the answer to the query for lines
and
to the solution.
Let represent the number of lines with a slope equal to the slope of line
. Then the number of lines with a slope different than the slope of lines
and
is
. The values of
can be preprocessed in the complexity of
with simple sorting, which brings us to the solution of complexity
.
For a solution valid for of points, introduce two new functions:
and
which tell us how many lines there are with slopes strictly greater or strictly smaller than the slope of line
. These functions can also be easily preprocessed in the complexity of
with the help of sorting. The number of triangles where the line
belongs and has the middle slope size can be calculated as
. For the final solution, we only need to sum these values for each
from
to
. The total complexity is
.
Comments