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$ ~M~ steepnesses (with taking into account duplicate steepnesses) separately. If some arbitrary point $(x_1, y_1)$ ~(x_1, y_1)~ and point $(x_2, y_2)$ ~(x_2, y_2)~ form a line with gradient $\frac{k}{d}$ ~\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 \end{align*}$

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

Implementation details are left to the reader as an exercise.

Time Complexity: $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~

Comments

1

LeonLiur commented on Dec. 29, 2021, 7:12 p.m.

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

2

sjay05 commented on Dec. 29, 2021, 10:54 p.m. ← edit 2 →

When solving for a particular slope $\frac{k}{d}$ ~\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$ ~v~ with frequency $f$ ~f~ you can form $\frac{f(f-1)}{2}$ ~\frac{f(f-1)}{2}~ distinct pairs of points with slope $\frac{k}{d}$ ~\frac{k}{d}~.

For further help, ask in the DMOJ Discord.

0

LeonLiur commented on Dec. 30, 2021, 12:06 a.m.

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