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表示。然后我的想法是搞一个哈希表，对于每一个点，都把这四种情况在坐标轴上的交点的map加1。最后遍历一下map，看看哪个map的值最大。
比如有个(3, 3)点的话，那就map[(3,0)]，map[(3,1)]++，map[(6,2)]++，map[(0,3)]++。写了如下代码…然后发现自己TM就没看懂题目…

/**
 * 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() == 0)
            return 0;
        map<string, int> m;
        int n = points.size();
        for (int i=0; i<n; i++) {
            int x = points[i].x;
            int y = points[i].y;
            stringstream n1;
            stringstream n2;
            stringstream n3;
            stringstream n4;
            n1 << x;
            n2 << y;
            n3 << x-y;
            n4 << x+y;
            m[n1.str()+",0"]++;
            m[n2.str()+",1"]++;
            m[n3.str()+",2"]++;
            m[n4.str()+",3"]++;
        }
        int res = 0;
        map<string, int>::iterator iter;
        for (iter=m.begin(); iter!=m.end(); iter++) {
            res = max(res, iter->second);
        }
        return res;
    }
};

gg了，不知道怎么做，看看大神们的做法吧。

/**
 * 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 n = points.size();
        int res = 0;
        for (int i=0; i<n; i++) {
            unordered_map<long double, int> map;
            int duplicate = 0, vertical = 1;
            int x1 = points[i].x, y1 = points[i].y;
            int local = 1;
            for (int j=i+1; j<n; j++) {
                int x2 = points[j].x, y2 = points[j].y;
                if (x1 == x2) {
                    if (y1 == y2)
                        duplicate++;
                    else
                        vertical++;
                }
                else {
                    long double slope = (long double)(y2 - y1) / (x2 - x1);
                    map[slope] = (map[slope] == 0) ? 2 : map[slope] + 1;
                    local = max(local, map[slope]);
                }
            }
            local = max(local+duplicate, vertical+duplicate);
            res = max(res, local);
        }
        return res;
    }
};

其实想法很直接，就是对于每一个点，计算另外的点和该点组成的线上有多少个点。然后处理下重复点和与x轴垂直的线的点。另外还得考虑到精度问题，假如用double表示斜率的话有可能会出问题…
比如

94911149/94911150 == 94911150/94911151  # false
94911150/94911151 == 94911151/94911152  # true
94911151/94911152 == 94911152/94911153  # false

这种情况，double尾数52位，精度是15位，有可能会导致出错。用long double的话可以AC，不过这样感觉也不太好，要是数值更大了，那还是会发生问题。
所以呢，得用更安全的办法来表示斜率，那就是pair<int, int>。当然得除下最大公约数，比如(8, 4) and (2, 1)都用(2, 1)表示。
原封不动把代码搬过来了…

class Solution { 
public: 
    int maxPoints(vector<Point>& points) {
        map<pair<int, int>, int> slopes;
        int maxp = 0, n = points.size();
        for (int i = 0; i < n; i++) {
            slopes.clear();
            int duplicate = 1;
            for (int j = i + 1; j < n; j++) {
                if (points[j].x == points[i].x && points[j].y == points[i].y) {
                    duplicate++;
                    continue;
                }
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                int dvs = gcd(dx, dy);
                slopes[make_pair(dx / dvs, dy / dvs)]++;
            }
            maxp = max(maxp, duplicate); 
            for (auto slope : slopes)
                if (slope.second + duplicate > maxp)
                    maxp = slope.second + duplicate;
        } 
        return maxp;
    }
private:
    int gcd(int num1, int num2) {
        while (num2) {
            int temp = num2; 
            num2 = num1 % num2;
            num1 = temp;
        }
        return num1;
    }
};

刷题备受打击，但是还是得继续刷刷刷，不然找不到实习了…