Max Points on a Line

leetcode

Max Points on a Line

题目链接

题目大意:

给定一些点(二维)的集合, 找出位于同一条直线的点的个数的最大值

Code
reference

/**
 * 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) {
        double slope;
        int maxNum = 0;
        double nSlope;
        int size = points.size();
        // if the number of the points is less than 3
        // then directly return it
        // since more than 1 point makes a line
        if(size < 3) {
            return size;
        }
        for(int i = 0; i < size; i++) {
            int rep = 0;
            // slope -> count
            std::map<double, int> lines;
            for(int j = 0; j < size; j++) {
                if(i == j) {
                    continue;
                }
                // replication
                if(points[i].x == points[j].x 
                        && points[i].y == points[j].y) {
                    rep++;
                    continue;
                }
                // x1 == x2
                // in this case, it can compute the slope
                // which is oo (infinity)
                // so use INT_MIN or INT_MAX to record this case
                // here use INT_MIN
                if(points[i].x == points[j].x) {
                    lines[INT_MIN]++;
                } else {
                    slope = (points[i].y - points[j].y) 
                            / (points[i].x - points[j].x + 0.);
                    lines[slope]++;
                }
            }
            // statistic & maybe lines is empty
            if(lines.size() == 0) {
                maxNum = max(maxNum, rep);
                continue;
            }
            // statistic
            std::map<double, int>::iterator iter;
            for(iter = lines.begin(); iter != lines.end(); iter++) {
                if(iter->second + rep > maxNum) {
                    maxNum = iter->second + rep;
                    nSlope = iter->first;
                }
            }
        }   
        // don't forget that plus the point itself
        return maxNum + 1; 
    }
};