# 149. 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.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

# Solution

Approach 1: For each point, calculate the slope of each other point with it.

# Code (Python)

Approach 1:

# Code (C++)

Approach 1:

class Solution {
private:
    int getGCD(int a, int b) {
        if (b == 0)
            return a;
        return getGCD(b, a % b);
    }
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n == 0)
            return 0;
        int res = 0;
        for (int i = 0; i < n; ++i)
        {
            int x1 = points[i][0];
            int y1 = points[i][1];
            int dup = 1;
            int subRes = 0;
            unordered_map<double,unordered_map<double,int>> umap;
            for (int j = i + 1; j < n; ++j)
            {
                int x2 = points[j][0];
                int y2 = points[j][1];
                if (x1 == x2 && y1 == y2)
                {
                    dup++;
                }
                else
                {
                    int diffX = x2 - x1;
                    int diffY = y2 - y1;
                    int diffGCD = getGCD(diffX, diffY);
                    diffX /= diffGCD;
                    diffY /= diffGCD;
                    umap[diffX][diffY]++;
                    subRes = std::max(subRes, umap[diffX][diffY]);
                }
            }
            res = std::max(res, subRes + dup);
        }
        return res;
    }
};