Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Have you met this question in a real interview?

 

 

Example

Given 4 points: (1,2), (3,6), (0,0), (1,3).

The maximum number is 3.

 

LeetCode上的原题，请参见我之前的博客。

 

解法一：

class Solution {public:    /**     * @param points an array of point     * @return an integer     */    int maxPoints(vector
     
      & points) {        int res = 0, n = points.size();        for (int i = 0; i < n; ++i) {            int duplicate = 1;            unordered_map
      
        m;            for (int j = i + 1; j < n; ++j) {                if (points[i].x == points[j].x && points[i].y == points[j].y) {                    ++duplicate;                } else if (points[i].x == points[j].x) {                    ++m[INT_MAX];                } else {                    double slope = (double)(points[j].y - points[i].y) / (points[j].x - points[i].x);                    ++m[slope];                }            }            res = max(res, duplicate);            for (auto it : m) {                res = max(res, it.second + duplicate);            }        }        return res;    }};
      
     

 

解法二：

class Solution {public:    /**     * @param points an array of point     * @return an integer     */    int maxPoints(vector
     
      & points) {        int res = 0, n = points.size();        for (int i = 0; i < n; ++i) {            int duplicate = 1;            map
      
       
        , int> m;            for (int j = i + 1; j < n; ++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) {                res = max(res, it.second + duplicate);            }        }        return res;    }    int gcd(int a, int b) {        return (b == 0) ? a : gcd(b, a % b);    }};
       
      
     

 

解法三：

class Solution {public:    /**     * @param points an array of point     * @return an integer     */    int maxPoints(vector
     
      & points) {        int res = 1;        for (int i = 0; i < points.size(); ++i) {            int repeat = 1;            for (int j = i + 1; j < points.size(); ++j) {                int cnt = 0;                int x1 = points[i].x, y1 = points[i].y;                int x2 = points[j].x, y2 = points[j].y;                if (x1 == x2 && y1 == y2) {++repeat; continue;}                for (int k = 0; k < points.size(); ++k) {                    int x3 = points[k].x, y3 = points[k].y;                    if (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3 == 0) {                        ++cnt;                    }                }                res = max(res, cnt);            }            res = max(res, repeat);        }        return points.empty() ? 0 : res;    }};