Max Points on a Line

基本思路是这样的， 每次迭代以某一个点为基准， 看后面每一个点跟它构成的直线， 维护一个HashMap， key是跟这个点构成直线的斜率的值， 而value就是该斜率对应的点的数量， 计算它的斜率， 如果已经存在， 那么就多添加一个点， 否则创建新的key。 这里只需要考虑斜率而不用考虑截距是因为所有点都是对应于一个参考点构成的直线， 只要斜率相同就必然在同一直线上。 最后取map中最大的值， 就是通过这个点的所有直线上最多的点的数量。 对于每一个点都做一次这种计算， 并且后面的点不需要看扫描过的点的情况了， 因为如果这条直线是包含最多点的直线并且包含前面的点， 那么前面的点肯定统计过这条直线了。 因此算法总共需要两层循环， 外层进行点的迭代， 内层扫描剩下的点进行统计， 时间复杂度是O（n^2), 空间复杂度是哈希表的大小， 也就是O（n),

 two flavors, the first one avoids dividing.
/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    struct Line {
        int a, b, c;
        Line(int _a=0, int _b=0, int _c=0) : a(_a), b(_b), c(_c) {}
        bool operator==(const Line &l) const {
            return a==l.a && b==l.b && c==l.c;
        }
    };
    struct LineHasher {
        size_t operator()(const Line &l) const {
            return 31*31*l.a + 31*l.b + l.c;
        }
    };
    int gcd(int x, int y) const {
        if (x<y) return gcd(y, x);
        if (y==0) return x;
        else return gcd(y, x%y);
    }
    Line solve(const Point &p1, const Point &p2) const { // get the line defined by two different points.
        Line l;
        if (p1.x==p2.x) {
            l.a=1; l.b=0; l.c=-p1.x;
        } else {
            l.b=p1.x-p2.x;
            l.a=(p2.y-p1.y);
            l.c=-(p2.y-p1.y)*p1.x-(p1.x-p2.x)*p1.y;

            int gcd1=gcd(abs(l.a), abs(l.b));
            int gcd2=gcd(abs(l.b), abs(l.c));
            int gcd3=gcd(gcd1, gcd2);
            l.a/=gcd3; l.b/=gcd3; l.c/=gcd3;
            if (l.b<0) {
                l.a*=-1; l.b*=-1; l.c*=-1;
            }
        }
        return l;
    }
    int maxPoints(vector<Point> &points) {
        unordered_map<Line, int, LineHasher> m_;
        int N=points.size(); int max_l=0;
        for (int i=0; i<N;i++) {
            m_.clear();
            int same_count=1;
            for (int j=i+1; j<N; ++j) {
                if (points[j].x == points[i].x && points[j].y == points[i].y) ++same_count;
                else {
                    Line l=solve(points[i], points[j]);
                    m_[l]++;
                }
            }
            for(auto it=m_.begin();it!=m_.end();++it){
                if(it->second+same_count>max_l)
                    max_l=it->second+same_count;
            }
            max_l<same_count?max_l=same_count:1;
        }
        return max_l;
    }
   
};

//second

 int maxPoints(vector<Point> &points) {
      unordered_map<float, int> statistic;
      int maxNum = 0;
      for (int i = 0; i< points.size(); i++)  {
          statistic.clear();
          statistic[INT_MIN] = 0; // for processing duplicate point
          int duplicate = 1;
          for (int j = i+1; j<points.size(); j++) {
              if (points[j].x == points[i].x && points[j].y == points[i].y) // count duplicate
              {
                  duplicate++; continue;
              }
              float key = (points[j].x - points[i].x) == 0 ? INT_MAX : // key for vertical line
             (float) (points[j].y - points[i].y) / (points[j].x - points[i].x);
              statistic[key]++; 
          }
          for (unordered_map<float, int>::iterator it = statistic.begin(); it != statistic.end(); ++it){
               if (it->second + duplicate >maxNum){
                   maxNum = it->second + duplicate;
               }
          }
      }
      return maxNum;
 }