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

 1 /*  2     Definition for a point 3 */ 4 // struct Point { 5 //     int x; 6 //     int y; 7 //     Point():x(0),y(0) {} 8 //     Point (int a, int b):x(0), y(0) {} 9 // };10 11 int maxPoints(vector<Point> &points) {12     if (points.empty())13         return 0;14     if (points.size() <= 2) 15         return points.size();16 17     int numPoints = points.size();18     map<double, int> pmap;    //存储斜率-点数对应值19     int numMaxPoints = 0;20 21     for (int i = 0; i != numPoints - 1; ++i) {22         int numSamePoints = 0, numVerPoints = 0;  //针对每个点分别做处理23         24         pmap.clear();25         26         for (int j = i + 1; j != numPoints; ++j) {27             if(points[i].x != points[j].x) {28                 double slope = (double)(points[j].y - points[i].y) / (points[j].x - points[i].x);29                 if (pmap.find(slope) != pmap.end())30                     ++ pmap[slope];   //具有相同斜率值的点数累加31                 else 32                     pmap[slope] = 1;33             }34             else if (points[i].y == points[j].y) 35                 numSamePoints ++;   //重合的点36             else37                 numVerPoints ++;    //垂直的点38 39         }40         map<double, int>::iterator it = pmap.begin();41         for (; it != pmap.end(); ++ it) {42             if (it->second > numVerPoints)43                 numVerPoints = it->second;44         }45         if (numVerPoints + numSamePoints > numMaxPoints) 46             numMaxPoints = numVerPoints + numSamePoints;47     }48     return numMaxPoints + 1;49 }