题目：

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

 

思路：

这道题看起来并不难，但是有很多需要注意的点，我用了很久的时间才通过这道题。大致的思路是这样的，使用穷举法，对于任意点P，计算其他点与点P的斜率。通过一次遍历，可以知道对于点P而言，每一个斜率值出现的次数，记录最高次数。遍历所有的节点，可以获得每一个节点所对应的次数。从中获取最大的次数再加1，即为一条直线上所有点的数目的最大值。需要注意的点为：

1.重复点

以(1,2),(2,3),(2,3),(1,2)为例。对于这4个点，在同一条直线上的点的最大数目为4。当节点遇到重复点时，需要记录重复点的数目，在最后的结果中直接加上该数目即可。

2.横坐标相同的点

由于斜率的公式为（y1-y2）/(x1-x2)，因此对于横坐标相同的点，无法计算斜率，需要额外使用一个变量保存横坐标相同的点。

3.精度问题

存在这样的测试用例，(0,0),(94911151,94911150),(94911152,94911151)。若按照斜率的计算公式，即使斜率为double类型，得到的(0,0)与(94911151,94911150)的斜率为1，(0,0)与(94911152,94911151)的斜率也为1。其实这三个点并不在同一条直线上，但是程序会认为这三个点在同一条直线上。所以，不能直接利用斜率判断三点是否位于同一条直线上。

换个思路想，我们可以计算(y1-y2)与(x1-x2)的最大公约数，再让(y1-y2)和(x1-x2)除以最大公约数，存入最终的(y1-y2)和(x1-x2)。若任意三个点的(y1-y2)和(x1-x2)相同，则证明它们位于同一条直线上。

 

代码：

1 struct Point { 2 int x; 3 int y; 4 Point() : 5 x(0), y(0) { 6 } 7 Point(int a, int b) : 8 x(a), y(b) { 9 } 10 }; 11 12 class Solution { 13 public: 14 int maxPoints(vector<Point>& points) { 15 if (points.size() <= 2) 16 return points.size(); 17 18 int max = 0; 19 for (unsigned int i = 0; i < points.size(); i++) { 20 map<pair<int, int>, int> slope; 21 22 double x1 = (double) points[i].x; 23 double y1 = (double) points[i].y; 24 25 int samex = 0; 26 int same = 0; 27 for (unsigned int j = 0; j < points.size(); j++) { 28 if (i == j) 29 continue; 30 31 double x2 = (double) points[j].x; 32 double y2 = (double) points[j].y; 33 34 if (x1 == x2 && y1 == y2) 35 same++; 36 else if (x1 == x2) 37 samex++; 38 else { 39 int num1 = y1 - y2; 40 int num2 = x1 - x2; 41 int common = gcd(num1, num2); 42 num1 /= common; 43 num2 /= common; 44 slope[pair<int, int>(num1, num2)]++; 45 } 46 } 47 int local_max = 0; 48 for (map<pair<int,int>, int>::iterator it = slope.begin(); 49 it != slope.end(); it++) { 50 if (it->second > local_max) 51 local_max = it->second; 52 } 53 if (samex > local_max) 54 local_max = samex; 55 local_max += same; 56 if (local_max > max) 57 max = local_max; 58 } 59 return max + 1; 60 } 61 62 int gcd(int num1, int num2) { 63 if (num2 == 0) 64 return num1; 65 return gcd(num2, num1 % num2); 66 } 67 };

 

转载于:https://www.cnblogs.com/sindy/p/8284215.html

相关资源：数据结构—成绩单生成器