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.
http://www.lintcode.com/en/problem/max-points-on-a-line/

Discussion

统计斜率出现的频率，然后选出频率最高的那个出现了多少次。因为计算频率的时候需要两个点，那统计问题就成了：给定任意一个点A，统计它与其余点的频率，这显然是个二层循环。比较trick的地方就在于：斜率有可能不存在，更特殊的还有可能其余点有可能跟A相同。

Solution

class Solution {
public:
    /**
     * @param points an array of point
     * @return an integer
     */
    int maxPoints(vector<Point>& points) {
        unordered_map<double, int> slope_cnt;
        int max_num = 0;
        for(int i=0; i<points.size(); i++) {//for each point
            //given point points[i], A
            int same = 1;
            for(int j=i+1; j<points.size(); j++) {
                //count solpes, 3 cases
                //1. same points
                if(points[j].x == points[i].x && points[j].y == points[i].y) {
                    same++;
                } else {
                    double slope = INT_MAX;//2. no slope --> (1,2), (1, 5)
                    //3. slope
                    if(points[j].x != points[i].x) {
                        double dx = points[j].x - points[i].x;
                        double dy = points[j].y - points[i].y;
                        slope = dy / dx;
                    }
                    slope_cnt[slope]++;
                }
            }
            //count frequency of slopes of A with other points
            int local_max_sum = same;
            for(auto v : slope_cnt) {
                local_max_sum = max(local_max_sum, same+v.second);
            }
            max_num = max(local_max_sum, max_num);
            slope_cnt.clear();
        }
        return max_num;
    }
};