149. Max Points on a Line

这道题给出二维平面上几个点的坐标，求最多有多少点共线。

这道题就是暴力方法，两重循环，求和每个点共线的点最多有多少个。

但是这个题的难点在于：

1.给出的点有重复，也要算到共线点里面去。两个重合的点也是共线的。

2.与y轴平行的线没有斜率，这个可以用INT_MAX来表示

3.由于通过斜率来判断共线需要用到除法，而用double表示的双精度小数在有的系统里不一定准确，为了更加精确无误的计算共线，我们应当避免除法，从而避免无线不循环小数的出现，那么怎么办呢，我们把除数和被除数都保存下来，不做除法，但是我们要让这两数分别除以它们的最大公约数，这样例如8和4，4和2，2和1，这三组商相同的数就都会存到一个映射里面，同样也能实现我们的目标。用斜率的话，

[[0,0],[94911151,94911150],[94911152,94911151]]

这个例子会通不过。

gcd是求a和b的最大公约数。两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。即一步步的降低两个数的值，直到其中一个变成零，这时所剩下的还没有变成零的数就是两个数的最大公约数。

/**
 * 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:
    int maxPoints(vector<Point>& points) {
        int res = 0;
        for (int i = 0; i < points.size(); ++i) {
            map<pair<int, int>, int> m;
            int duplicate = 1;
            for (int j = i + 1; j < points.size(); ++j) {
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    ++duplicate; continue;
                } 
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                int d = gcd(dx, dy);
                ++m[{dx / d, dy / d}];
            }
            res = max(res, duplicate);
            for (auto it = m.begin(); it != m.end(); ++it) {
                res = max(res, it->second + duplicate);
            }
        }
        return res;
    }
    int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
};

如果想不到最大公约数，可以分开讨论k为正无穷，k正常，和点重复的情况。

/**
 * 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:
    int maxPoints(vector<Point> &points) {
        if(points.size() < 3)	return points.size();
        int res = 0;
        for(int i = 0; i < points.size(); ++i){
            int dup = 0;
            int straight = 0;
            int curmax = 1;
            map<double, int> m;
            for(int j = 0; j < points.size(); ++j){
                if(i == j)	continue;
                if(points[i].x == points[j].x && points[i].y == points[j].y)
                {
                    dup++;
                }
                else if(points[i].x == points[j].x){
                    if(straight == 0)	straight = 2;
                    else straight++;
                    curmax = max(straight,curmax);
                }
                else{
                    double k = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);
                    if(m[k] == 0)	m[k] = 2;
                    else m[k]++;
                    curmax = max(curmax, m[k]);
                }
            }
            res = max(res, curmax + dup);
        }
        return res;
    }
};