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;
}
};
