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)~