149 Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
0 1 2 3 4
| o o
| o o
0 1 2 3 4 5 6
A slope can be calculated between two given points. Each slope represents a straight line. For each straight line, bring in all the points to see if they are collinear and calculate the number.
Two special cases need to be considered.
One is that when two points coincide, a straight line cannot be determined, but this is also a collinear case and requires special treatment.
The second is the case where the slope does not exist. Since the slope k of the two points (x1, y1) and (x2, y2) is expressed as (y2-y1) / (x2-x1), then the slope does not exist when x1 = x2, This collinear situation requires special treatment
TreeMap is used to record the mapping between the slope and the number of collinear points. The first case of coincident points assumes its slope is INT_MIN, and the second case assumes its slope is INT_MAX, so TreeMap can be used for mapping. A variable duplicate is also needed to record the number of coincident points, and finally only needs to be added to the number in the TreeMap to get the total number of collinear points.