Max Points on a Line--LeetCode-蒲公英云

Max Points on a Line--LeetCode

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

思路：二维坐标上的点，最多的共线的点数。

共线：要么是垂直X轴，要么垂直与Y轴，要么就是斜线，一个坐标点，按照X排序，比较垂直与X轴的最多的点，按照Y轴排序，比较垂直Y轴的最多的点。

至于怎么看斜线。

任意一条直线都可以表述为

y = ax + b

假设，有两个点(x1,y1), (x2,y2)，如果他们都在这条直线上则有

y1 = kx1 +b

y2 = kx2 +b

由此可以得到关系，k = (y2-y1)/(x2-x1)。即如果点c和点a的斜率为k, 而点b和点a的斜率也为k，可以知道点c和点b也在一条线上。

取定一个点points[i], 遍历其他所有节点, 然后统计斜率相同的点数，并求取最大值即可

对于任意一个点，和其他任意不同的点存在斜线斜率，看某个斜率的个数，然后对所有的点都这样操作，最后找到最多的点数。

int maxPoints(vector<pair<int,int> > &points)
{
    if(points.size() <=2)
     return points.size();
    int maxnum=0;
    double temp,X,Y;
    int i,j,same;
    sort(points.begin(),points.end(),compY);
    for(i=0;i<points.size();)
    {
       for(j=i+1;j<points.size();j++)
           if(points[j].second != points[i].second)
           {
              maxnum = max(maxnum,j-i);
              break;
           }                  
       i = j;               
    }
    sort(points.begin(),points.end(),compX);
    for(i=0;i<points.size();)
    {
       for(j=i+1;j<points.size();j++)
           if(points[j].first != points[i].first)
           {
                 maxnum = max(maxnum,j-i);   
                 break;
           }                
       i = j;               
    }
     if(points[points.size()-1].first -points[0].first < maxnum)
     return maxnum;
    for(i=0;i<points.size();i++)
    {
      same =1;
      map<double,int> flip;
      flip.clear();
      for(j=0;j<points.size();j++)
      {
          if(i == j)
           continue;
          if(points[i].first==points[j].first&&points[i].second==points[j].second)
          {
             same++;
             continue;
          } 
          if(points[i].first != points[j].first && points[i].second != points[j].second)
          {
             X= points[i].first - points[j].first;
             Y= points[i].second- points[j].second;
             temp = X/Y;
             flip[temp]++; 
          }     
      }
      map<double,int>::iterator it = flip.begin();  
      for(; it != flip.end(); it++)  
            if(it->second + same > maxnum)  
                maxnum = it->second + same;                               
    }
     return maxnum;
}