Editorial for An Animal Contest 4 P3 - Snowy Slopes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: sjay05

Consider all M steepnesses (with taking into account duplicate steepnesses) separately. If some arbitrary point (x_1, y_1) and point (x_2, y_2) form a line with gradient \frac{k}{d}:

\displaystyle \frac{y_2-y_1}{x_2-x_1} = \frac{k}{d}

By manipulating the equation:

\displaystyle \begin{align*}
k(x_2-x_1) &= d(y_2-y_1) \\
kx_2-kx_1 &= dy_2-dy_1 \\
kx_1-dy_1 &= kx_2-dy_2

Let id(k, d, i) of a point i with coordinate (x, y) be kx-dy. In other words, for two points a and b to form a line with gradient \frac{k}{d}, id(k, d, a) must be equal to id(k, d, b).

Implementation details are left to the reader as an exercise.

Time Complexity: \mathcal{O}(NM)


  • 0
    LeonLiur  commented on Dec. 29, 2021, 2:12 p.m.

    How would you count the amount of same values inside the id array?

    • 1
      sjay05  commented on Dec. 29, 2021, 5:54 p.m. edit 2

      When solving for a particular slope \frac{k}{d}, we can maintain the id's in a map <id value, frequency (# of points with that id value)>. For a id value v with frequency f you can form \frac{f(f-1)}{2} distinct pairs of points with slope \frac{k}{d}.

      For further help, ask in the DMOJ Discord.

      • -1
        LeonLiur  commented on Dec. 29, 2021, 7:06 p.m.

        ah, ok, thanks a lot, for some reason I was thinking f frequency would form f! pairs, thanks a lot