Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Method I
解决思路和求最短不减子序列类似：
开一个数组lines，第k个位置存放的是有k个点的直线，由于这样的直线可能有多条，所以需要嵌套vector。
每来一个新点，都要把它加到k=1的位置。这里是把一个点也当成一条直线。
如果当前点在有k个点的直线上，那么令k=k+1，把lines[k]中包含当前点的直线加到lines[k + 1]中。
否则，从k-1往回找到j，找到lines[j]为包含当前点的最长直线集，将其中包含包含当前点的直线都加到lines[j+1]中；
这里有几点要注意：
1. 每次遇到一个新点，如果它没有出现过，需要把它当成一条直线加到lines[1]中；如果已经出现过，就要把它加到lines[2]中；比如(1,1)这个点出现了两次，第一次把它加到lines[1]中，第二次，由于(1,1)-(1,1)实际包括了两个点了，所以要把它加到lines[2]中。
2. 在判断目标点是否在直线集上时需要分情况处理。当遇到直线集中的某条直线其实只是一个点，比如(1, 1) - (1,1)，那么目标点肯定是在这条“直线”上的，生成的新的直线要尽量让直线的两个端点不一样。假设目标点为(2, 1)，生成的新的直线就应该为(2, 2) - (1,1)；这才是一条具有三个点的直线((2,2), (1,1), (1, 1))。如果还是生成(1,1）- (1,1)这条直线，那么当再来一个新的点(3,4)时，我们就会认为(3,4)仍在(1,1)-(1,1）这条线上，因此会生成拥有4个点的直线，这样就出错了。
1 struct Point { 2 int x; 3 int y; 4 Point() : x(0), y(0) {} 5 Point(int a, int b) : x(a), y(b) {} 6 }; 7 8 bool inLine(Point &p, pair &line) { 9 return (p.y - line.first.y) * (line.second.x - line.first.x) == 10 (line.second.y - line.first.y) * (p.x - line.first.x);11 }12 13 bool inLines(Point p, vector > &lines, vector > &ret) {14 bool isInLines = false;15 for (vector >::iterator it = lines.begin(); it != lines.end(); ++it) {16 if (inLine(p, *it)) {17 if (it->first.x != it->second.x || it->first.y != it->second.y) {18 ret.push_back(*it);19 } else if (p.x != it->first.x || p.y != it->first.y) {20 ret.push_back(pair (p, it->first));21 } else {22 ret.push_back(*it);23 }24 isInLines = true;25 }26 }27 return isInLines;28 }29 30 void print(vector > > &lines, int k) {31 cout << k << "-----------------------------------------------" << endl;32 for (int j = 0; j < lines[k - 1].size(); ++j) {33 cout << lines[k - 1][j].first.x << " " << lines[k - 1][j].first.y << "-"34 << lines[k - 1][j].second.x << " " << lines[k - 1][j].second.y << endl;35 } 36 cout << k << "-----------------------------------------------" << endl;37 }38 int maxPoints(vector &points) { 39 int n = points.size();40 if (n <= 2) return n;41 42 vector > > lines;43 vector > l;44 l.push_back(pair (points[0], points[0]));45 lines.push_back(l);46 int k = 1;47 48 for (int i = 1; i < n; ++i) {49 //cout << i << endl;50 vector > ps;51 if (inLines(points[i], lines[k - 1], ps)) {52 lines.push_back(ps); 53 k++;54 //print(lines, k);55 } else {56 for (int j = k - 2; j >= 0; --j) {57 vector > ps;58 if (inLines(points[i], lines[j], ps)) {59 lines[j + 1].insert(lines[j + 1].end(), ps.begin(), ps.end());60 //print(lines, j + 1);61 break;62 }63 }64 }65 66 bool isExist = false;67 for (int j = 0; j < lines[0].size(); ++j) {68 if (lines[0][j].first.x == points[i].x69 && lines[0][j].first.y == points[i].y) {70 isExist = true;71 break;72 }73 }74 75 if (!isExist) {76 lines[0].push_back(pair (points[i], points[i]));77 } else {78 lines[1].push_back(pair (points[i], points[i]));79 }80 }81 82 //print(lines, k);83 return k;84 } 8ms Accepted.
Method II
对每个点，计算它和其他点的斜率，如果斜率相同，证明这n个点在同一个直线上。这样就可以找到包含某个点的最大点集。然后再取最大就行了。
注意： 处理好重复点和垂直点。第i个点只需要和i+1之后的点比较。因为i之前的点都计算过了。时间复杂度O(n^2)。 80ms accepted，略慢。
1 /** 2 * Definition for a point. 3 * struct Point { 4 * int x; 5 * int y; 6 * Point() : x(0), y(0) {} 7 * Point(int a, int b) : x(a), y(b) {} 8 * }; 9 */10 class Solution {11 public:12 int maxPoints(vector &points) {13 int n = points.size();14 if (n == 0) return 0;15 16 unordered_map lines;17 int max = 1;18 for (int i = 0; i < n; ++i) {19 lines.clear();20 21 int dup = 1, m = 0;22 for (int j = i + 1; j < n; ++j) {23 if (points[i].x != points[j].x) {24 double k = (points[i].y - points[j].y) * 1.0 / (points[i].x - points[j].x);25 lines[k]++;26 if (lines[k] > m) m = lines[k];27 } else if (points[i].y != points[j].y) {28 lines[0]++;29 if (lines[0] > m) m = lines[0];30 } else {31 dup++;32 }33 }34 if (m + dup > max) max = m + dup;35 }36 37 return max;38 }39 };