| Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. |
Analysis:
Get lines passing every two, and compare.
If we get all of them n*(n-1)/2, then we still need compare them all. that will be O(n^4).
By using map, and round function, we need to check just the lines with the same property.
But to store a line, at least two property are needed, either two points, or slope and intersect. And compare them is still boring and time consuming. we could use nested map, but we try to avoid that.
what about calculating all line passing by the same point, store those lines' slope in map and check for only once.O(n) for each node. And O(n^2) totally. Not a bad idea. Let's try it.
