【Max Points on a Line 】cpp

题目：

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

代码：

/**
 * 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) {
            // least points case
            if ( points.size()<3 ) return points.size();
            // search for max points
            int global_max_points = 1; 
            map<double, int> slope_counts;
            for ( int i=0; i<points.size(); ++i )
            {
                slope_counts.clear();
                int same_point = 0;
                int local_max_point = 0;
                for ( int j=0; j<points.size(); ++j )
                {
                    // the exactly same point
                    if ( j==i ) continue;
                    // initial as the same x case
                    double slope = std::numeric_limits<double>::infinity();
                    // same point case
                    if ( points[i].x==points[j].x && points[i].y==points[j].y )
                    { same_point++; continue; }
                    // normal case
                    if ( points[i].x!=points[j].x ) 
                    { slope = 1.0*(points[i].y - points[j].y) / (points[i].x - points[j].x); }
                    // increase slope and its counts
                    slope_counts[slope] += 1;
                    // update local max point
                    local_max_point = std::max(local_max_point, slope_counts[slope]);
                }
                // add the num of same point to local max point
                local_max_point = local_max_point + same_point + 1;
                // update global max point
                global_max_points =  std::max(global_max_points, local_max_point);
            }
            return global_max_points;
    }
};

tips：

以每个点为中心 & 找到其余所有点与该点构成直线中斜率相同的，必然为多点共线的

几个特殊case:

1. 相同点 （保留下来坐标相同的点，最后计算最多共线的点时补上这些相同点的数量）

2. x坐标相等的点 （定义slope为double 无穷大）

3. 每次在更新local_max_point时，不要忘记加上1（即算上该点本身）

===================================

学习一个提高代码效率的技巧，如果线段points[i]~points[j]在最多点的直线上，那么线段points[j]~points[i]也在最多点的直线上，所以j=i+1开始即可。

/**
 * 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) {
            // least points case
            if ( points.size()<3 ) return points.size();
            // search for max points
            int global_max_points = 1; 
            map<double, int> slope_counts;
            for ( int i=0; i<points.size()-1; ++i )
            {
                slope_counts.clear();
                int same_point = 0;
                int local_max_point = 0;
                for ( int j=i+1; j<points.size(); ++j )
                {
                    // initial as the same x case
                    double slope = std::numeric_limits<double>::infinity();
                    // same point case
                    if ( points[i].x==points[j].x && points[i].y==points[j].y )
                    { same_point++; continue; }
                    // normal case
                    if ( points[i].x!=points[j].x ) 
                    { slope = 1.0*(points[i].y - points[j].y) / (points[i].x - points[j].x); }
                    // increase slope and its counts
                    slope_counts[slope] += 1;
                    // update local max point
                    local_max_point = std::max(local_max_point, slope_counts[slope]);
                }
                // add the num of same point to local max point
                local_max_point = local_max_point + same_point + 1;
                // update global max point
                global_max_points =  std::max(global_max_points, local_max_point);
            }
            return global_max_points;
    }
};

tips：

减少了内层循环的遍历次数，提高了程序运行效率。

=====================================

第二次过这道题，上来想到了正确的思路，但是没有敢肯定；注意samePoints和算上当前点本身。

/**
 * 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) {
            if (points.empty()) return 0;
            map<double, int> slopeCount;
            int globalMax = 1;
            for ( int i=0; i<points.size(); ++i )
            {
                slopeCount.clear();
                int samePoints = 0;
                int x = points[i].x;
                int y = points[i].y;
                for (int j=i+1; j<points.size(); ++j )
                {
                    int xx = points[j].x;
                    int yy = points[j].y;
                    if ( xx==x && yy==y )
                    {
                        samePoints++;
                        continue;
                    }
                    if ( xx==x )
                    {
                        slopeCount[numeric_limits<double>::infinity()]++;
                        continue;
                    }
                    slopeCount[1.0*(y-yy)/(x-xx)]++;
                }
                // count max
                int local = 0;
                for ( map<double, int>::iterator i=slopeCount.begin(); i!=slopeCount.end(); ++i )
                {
                    local = max(local, i->second);
                }
                globalMax = max(globalMax,local+samePoints+1);
            }
            return globalMax;
    }
};