好久没做直线的题了,只能说仍然不擅长。。。
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
//如果你要存储每一条直线,也就是要有斜率和截距很麻烦,但是如果是通过每一个点的直线那就可以
//为每一个直线开一个map
if (points.size() < 3) {
return points.size();
}
int res=0;
int maxn=1000000000;
for(int i=0;i<points.size();i++){
map<double,int>record;
int samepoint=0;
for(int j=0;j<points.size();j++){
if(j==i)continue;//跳过当前的点
if(points[j]==points[i]){
//两个相同的点
samepoint++;
}
//考虑x=1和y=0两种特殊情况
else if(points[i][0]==points[j][0]){
record[maxn]++;
}else if(points[i][1]==points[j][1]){
record[0]++;
}else{
// 记录其他斜率的点
double slope = (double)(points[i][1] - points[j][1])
/ (double)(points[i][0] - points[j][0]);
++record[slope];
}
}
int cur_max = INT_MIN;
for (auto it : record) {
cur_max = max(cur_max, it.second);
}
res = max(res, samepoint + cur_max + 1);
}
return res;
}
};