/** * 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 size = points.size(); int maxNum = 0; unordered_map<float, int> map; for(int i=0;i<size;i++) { map.clear(); int dup = 1; for(int j=0;j<size;j++) { if(i == j) continue; if(points[j].x == points[i].x && points[j].y == points[i].y) {dup++;continue;} float k = points[j].x == points[i].x ? INT_MAX: (float)(points[j].y-points[i].y)/(float)(points[j].x - points[i].x); map[k] ++; } for(auto itor : map) { maxNum = max(itor.second + dup, maxNum); } if(map.size() == 0) maxNum = max(dup, maxNum); } return maxNum; } };
Friday, May 8, 2015
[LeetCode] 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.
Analysis:
Just need to handle the duplicate node and vertical lines.