[Leetcode] Max Points on a Line

Problem 

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Algorithm

A 2D line has an equation y = k*x + m, where k is the slope and m is the intercept. Naturally, we can create a Line class to represent a line, with a field slope and a field intercept. Two lines are identical only if their have the same slope and intercept.  Special case, when the line is parallel to the y axis, its slope is infinity. Different lines parallel to y axis have different intercept (the intercept changed its meaning here). 

With this Line class, we compute O(n^2) lines formed by O(n) points. Using a hash map <Line, Count>, we can record the occurrence of each line. After the iteration, we can find the line with max count. 

The Online Judge of Leetcode has test cases containing duplicate input points. This makes the simple formula,  nLines =  nPoints*(nPoints-1)/2, does not work.  Therefore, we need to check the input points one by one, to see if it is on the max count line. 

We need to test the equality of two lines. When checking, it uses the hashCode method first, then the equals method. Therefore, we should override both hashCode and equals method. Pay attention to how to implement the hashCode and equals methods. 

Code