Friday, March 7, 2014

Day 75, ##, 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.
---------------------------------------------------------------------------------
O(n^2)
/**
 * 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 maxP = 2;
        if (points.size() == 0 || points.size() == 1) return points.size();
 
        for (int i = 0; i < points.size(); i++) {
            unordered_map<double,int> slopes;
            int samex = 1;
            int samePoints = 0;
            int curMax = 0;
             
            for (int j = i + 1; j < points.size(); j++) {
                double xdistance = points[i].x - points[j].x;
                double ydistance = points[i].y - points[j].y;
                if (xdistance == 0 && ydistance == 0) {
                    samePoints++;
                    continue;
                }else if (xdistance == 0) {
                    samex++;
                    continue;
                }
                 
                double slope = ydistance / xdistance;
                 
                if (slopes.find(slope) == slopes.end()) {
                    slopes[slope] = 2;
                }else {
                    slopes[slope]++;
                }
             
                curMax = max(curMax,max(samex,slopes[slope]));
            }

            curMax = max(samex,curMax);
            maxP = max(maxP,curMax + samePoints);
        }
        return maxP;
    }
     
};