题目：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.
这道题需要稍微转变一下思路，用斜率来实现，试想找在同一条直线上的点，怎么判断在一条直线上，唯一的方式也只有斜率可以完成，我开始没想到，后来看网友的思路才想到的，下面是简单的实现：
其中有一点小技巧，利用map<double, int>来存储具有相同斜率值的的点的数量，简洁高效。
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 else 37 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 }
