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: ZQFMGB12
First, note that a linear transformation is not the same as a function with a linear graph, that is, a function in the form of 
~f(x) = mx+b~.
We deduce a few properties about 
~T~. First, we see that 
~T(0) = T(0x) = 0T(x) = 0~. Also, 
~T(x) = T(1x) = xT(1)~. If we let 
~m = T(1)~, then we see that 
~T(x) = mx~ for some 
~m~. It can be easily proven that the first property 
~T(x+y) = T(x)+T(y)~ still holds.
Exercise: show that when ~T~ only satisfies the first condition, then it does not need to be in the form ~T(x) = mx~. Would this solution still be correct?
Therefore, we simply need to check if all points are on the same graph ~T(x) = mx~ for some ~m~. The implementation is not very difficult, but do be wary of the corner case where 
~x = 0~.
Failing to resolve the ~x = 0~ corner case resulted in 
~25\%~ of the points, and a slow all-pairs comparison of slope was awarded 
~50\%~ of the points.
Time Complexity: 
~\mathcal{O}(N)~
Comments