149. Max Points on a Line.md

149. Max Points on a Line

1.Description

给定一些平面上的点，求一条直线，使得经过的点数最多。

2.Solution

因为平面上点数有限多，所以构成的可能直线集合也是有限大的。

所以枚举平面上的点对$ (p_{1}, q_{1}) $和$ (p_{2}, q_{2}) $，构成一条直线$u$，判断其他点是否在$u$上即可。

判断是否共线时可以用交叉相乘代替除法运算。

3. Source Code

#include <vector>
#include <set>
#include <map>

using point = std::pair<int, int>;

inline bool check_on_line(const point &p, const point &q, const point &x) {
    const long r1 = (x.second - p.second);
    const long r2 = (x.first - q.first);
    const long u1 = (x.first - p.first);
    const long u2 = (x.second - q.second);
    return r1 * r2 == u1 * u2;
}

class Solution {
public:
    int maxPoints(std::vector<std::vector<int>> &points) {
        const auto n = points.size();
        // 平面上点数小于等于2时 最大共线点数跟既有点数一样多
        if (n <= 2) {
            return n;
        }

        auto points_count = std::map<point, unsigned int>();
        
        // 重合点统计
        for (auto &r: points) {
            const point p = {r[0], r[1]};
            auto at = points_count.find(p);

            if (at != points_count.end()) {
                points_count[p] += 1;
            } else {
                points_count[p] = 1;
            }
        }
        
        // 不重复的点个数
        const auto unique_n = points_count.size();
        
        // 同上
        if (unique_n <= 2) {
            return n;
        }

        auto max_points_num = 0;
        
        // 枚举点对
        for (auto &p: points_count) {
            for (auto &q: points_count) {
                // 起点终点不能一样
                if (p.first == q.first) {
                    continue;
                }
                
                // 初始共线点数等于在起点终点的点数之和（包括重合点）
                auto t = p.second + q.second;
                // 枚举第三点
                for (auto &k: points_count) {
                    // 不与起点终点一样
                    if ((k.first == p.first) or (k.first == q.first)) {
                        continue;
                    }
                    
                    // 共线判断
                    if (check_on_line(p.first, q.first, k.first)) {
                        // 若共线 把重合的所有点都加上
                        t += points_count[k.first];
                    }
                }
                
                // 更新最大值
                if (t > max_points_num) {
                    max_points_num = t;
                }
            }
        }
        
        return max_points_num;
    }
};