首页 > 代码库 > Max Points on a Line
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.
解题方案：
该题想不到其他好办法，唯有暴力破解，两点求斜率，如果斜率相同，意味着共线，然后求出最大共线点数，注意可能有重复的点，和斜率为正无穷的点。下面是该题的代码:
1 class Solution { 2 public: 3 int maxPoints(vector<Point> &points) { 4 map<double, int> result; 5 int max_line = 0; 6 double gradient;//斜率 7 int multi = 0; 8 for (vector<Point>::iterator ix = points.begin(); ix != points.end(); ++ix) { 9 result.clear();10 multi = 1;11 result[INT_MIN] = 0;12 for (vector<Point>::iterator jx = points.begin(); jx != points.end(); ++jx) {13 if (ix == jx) {14 continue;15 }16 if(ix->x == jx->x && ix->y == jx->y){17 ++multi;18 continue;19 }20 if(ix->x != jx->x){21 gradient = (double)(ix->y - jx->y) / (ix->x - jx->x);22 result[gradient]++;23 }else{24 result[INT_MAX]++;25 }26 }27 for (map<double, int>::iterator ix = result.begin(); ix != result.end(); ++ix){28 if (ix->second + multi > max_line) {29 max_line = ix->second + multi;30 }31 }32 }33 return max_line;34 }35 };
Max Points on a Line
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。