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.
/**
 * 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;
    }
};