题目：Max Points on a line
代码语言：javascript复制Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.这道题需要稍微转变一下思路，用斜率来实现，试想找在同一条直线上的点，怎么判断在一条直线上，唯一的方式也只有斜率可以完成，我开始没想到，后来看网友的思路才想到的，下面是简单的实现： 其中有一点小技巧，利用map<double, int>来存储具有相同斜率值的的点的数量，简洁高效。
代码语言：javascript复制 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 }
