Max Points on a Line

 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.

class Solution {

public:

    int maxPoints(vector<vector<int>>& points) 

    {

        int n=points.size();

        if(n<2)

            return n;

        unordered_map<string,int> pt;

        int maxv=1;

        

        for(int i=0;i<n-1;++i)

        {

            unordered_map<string,int> mp;

            int lmax=1;

            auto p=points[i];

            int same=0;

            for(int j=i+1;j<n&&(pt.find(to_string(points[i][0])+"-"+to_string(points[i][1]))==pt.end());++j)

            {

                auto q=points[j];

                if(p[0]==q[0]&&p[1]==q[1])

                {

                    ++same;

                    continue;

                }

                int x=(p[0]-q[0]),y=(p[1]-q[1]);

                int g=__gcd(x,y);

                string s=to_string(x/g)+"_"+to_string(y/g);

                if(mp.find(s)==mp.end())

                {

                    mp[s]=2;

                }else{

                    mp[s]++;

                }

                lmax=max(lmax,mp[s]);

            }

            pt[to_string(p[0])+"-"+to_string(p[1])]++;

            maxv=max(maxv,lmax+same);

            // cout<<endl;

        }

        return maxv;

    }    

};