leetcode练习题 max-points-on-a-line

解题思路

参考了讨论区的方案。首先二重循环，第一重循环的点作为基点，之后判断图中的其他点，图上的点可能是与基点在同一垂直线(斜率不存在),也有可能与基点重合，还有可能是普通的点，分三种情况，保留较大值。

代码

#include<map>
class Solution {
public:int maxPoints(vector<Point> &points) {if(points.size() == 0 || points.size() == 1)return points.size();int res = 0;for(int i = 0;i < points.size();i++){map<double,int>m;int curmax = 1;int vernum = 1;//垂直的点的数目，初始值为它本身int dup = 0;//重复点的数量for(int j = 0;j < points.size();j++){if(i != j){double y_t = points[i].y - points[j].y;double x_t = points[i].x - points[j].x;if(y_t == 0 && x_t == 0)dup++;else if(x_t == 0){vernum++;curmax = curmax > vernum ? curmax : vernum;}else{double t = y_t / x_t;if(m.find(t) == m.end())m[t] = 2;elsem[t]++;curmax = curmax > m[t] ? curmax : m[t];}}}res = res > (curmax + dup) ? res : curmax + dup;}return res;}
};