https://leetcode.com/problems/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.
Example 1:
Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: ^ | | o | o | o +-------------> 0 1 2 3 4
Example 2:
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Explanation: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6
用判断三点共线的办法 时间复杂度为 $O(n^3)$
代码：
/** * Definition for a point. * struct Point { * int x; * int y; * Point() : x(0), y(0) {} * Point(int a, int b) : x(a), y(b) {} * }; */ class Solution { public: int maxPoints(vector<Point>& points) { int n = points.size(); int res = 0; for(int i = 0; i < n; i ++) { int d = 1; for(int j = i + 1; j < n; j ++) { int cnt = 0; long long x1 = points[i].x, y1 = points[i].y; long long x2 = points[j].x, y2 = points[j].y; if(x1 == x2 && y1 == y2) {d ++; continue;} for(int k = 0; k < n; k ++) { int x3 = points[k].x, y3 = points[k].y; if(x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3 == 0) cnt ++; } res = max(res, cnt); } res = max(res, d); } return res; } };
#Leetcode# 149. Max Points on a Line
原文：https://www.cnblogs.com/zlrrrr/p/10057872.html
