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

• 解题思路

  若两个点共线，则有如下情况：
  • 两个点重合
  • 两个点的x坐标相同（斜率无穷大）
  • 两个点的斜率相同
    y1 = k * x1 + b;
    y2 = k * x2 + b;
    则有k = (y1 - y2) / (x1 - x2);

• 实现代码

/*****************************************************************    *  @Author   : 楚兴    *  @Date     : 2015/2/9 20:46    *  @Status   : Accepted    *  @Runtime  : 35 ms******************************************************************/#include 
     
      #include 
      
       struct Point {    int x;    int y;    Point() : x(0), y(0) {}    Point(int a, int b) : x(a), y(b) {}};class Solution {public:    int maxPoints(vector
       
         &points) {        if (points.size() <= 2)        {            return points.size();        }        int maxNum = 0;        unordered_map
        
          mymap;        int copy;  //重复的点个数        double k;  //斜率        for (int i = 0; i < points.size(); i++)        {            mymap.clear();            copy = 0;  //坐标相同点的个数            for (int j = 0; j < points.size(); j++)            {                if (j == i)                {                    continue;                }                if (points[i].x == points[j].x && points[i].y == points[j].y)                {                    copy++;  //相同点                    continue;                }                if (points[i].x == points[j].x)                {                    mymap[INT_MAX]++; //斜率不存在                }                else                 {                    k = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);                    mymap[k]++;                }            }            if (mymap.size() == 0)            {                maxNum = maxNum > copy ? maxNum : copy;            }            int temp;            for (auto it = mymap.cbegin(); it != mymap.cend(); it++)            {                temp = (*it).second + copy;                maxNum = maxNum > temp ? maxNum : temp;            }        }        return maxNum + 1;  //加上自身    }};int main(){    Solution s;    vector
         
           points;    Point* p1 = new Point(0, 0);    Point* p2 = new Point(0, 0);    points.push_back(*p1);    points.push_back(*p1);    cout<
          
           <