149. Max Points on a Line

The idea is pretty straightforward. We fix a point first and scan all the lines across the point. And then we move to next point. When calculating the lines for the next point, we don't need to first the previous points before it. Reason? When we visited previous point, we've calculated all the point on the same line including the current one. When we calculating the lines, we use hash map to store slope-count as key-pair. The trick here is we need to consider two special cases: 1. vertical lines and 2. duplicate points. Also the hash map should be used locally, i.e. for current point only. Why not globally? The reason is there are many parallel lines with the same slope.

1:  /**  
2:   * Definition for a point.  
3:   * struct Point {  
4:   *   int x;  
5:   *   int y;  
6:   *   Point() : x(0), y(0) {}  
7:   *   Point(int a, int b) : x(a), y(b) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    int maxPoints(vector<Point>& points) {  
13:      if (points.size() <= 2) return points.size();  
14:      int res = 0;  
15:      for (int i = 0; i < points.size(); i++) {  
16:        int duplicate = 0, vertical = 1, line = 1;  
17:        unordered_map<double, int> mapping;  
18:        for (int j = i+1; j < points.size(); j++) {  
19:          if (points[i].x == points[j].x) {  
20:            if (points[i].y == points[j].y) {  
21:              duplicate++;  
22:            } else {  
23:              vertical++;  
24:            }  
25:          } else {  
26:            double slope = (points[i].y-points[j].y)*1.0/(points[i].x-points[j].x);  
27:            mapping[slope] == 0 ? mapping[slope] = 2 : mapping[slope]++;  
28:            line = max(line, mapping[slope]);  
29:          }  
30:        }  
31:        res = max(res, max(line, vertical)+duplicate);  
32:      }  
33:      return res;  
34:    }  
35:  };