Description

给定\(n\)个整数点的二维坐标\((x_i, y_i)\),求最多的连在同一直线上的点数目。

Constraints

  • \(1 \le n \le 300\)
  • \(-10^4 \le x_i, y_i \le 10^4\)
  • 不存在重复的点

Solution

计算几何就从来没做过,还好这题思路简单。

哈希表配合gcd记录斜率即可。需要注意的是横竖两种情况要特殊维护。

Code

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        auto gcd = [](auto &&gcd, int a, int b) -> int {
            return b ? gcd(gcd, b, a%b) : a;
        };
        auto h = [](auto &&tup) {
            auto &&[x, y] = tup;
            auto make_hash = []<typename T>(T &&v) {
                return hash<decay_t<T>>{}(v);
            };
            return make_hash(x) ^ make_hash(y);
        };
        using Map = unordered_map<tuple<int, int>, int, decltype(h)>;
        int ans {};
        for(size_t i = 0; i < points.size(); ++i) {
            // special cases
            int sc1 {}, sc2 {};
            Map rec(0, h);
            for(size_t j = 0; j < i; ++j) {
                auto p1 = points[i], p2 = points[j];
                auto [x1, y1] = make_tuple(p1[0], p1[1]);
                auto [x2, y2] = make_tuple(p2[0], p2[1]);
                auto dx = x1 - x2, dy = y1 - y2;
                if(!dx || !dy) {
                    ++(dx ? sc1 : sc2);
                    continue;
                }
                bool neg = 0;
                if(dx < 0) neg ^= 1, dx = -dx;
                if(dy < 0) neg ^= 1, dy = -dy;
                int g = gcd(gcd, dx, dy);
                dx /= g; dy /= g;
                if(neg) dx = -dx;
                rec[make_tuple(dx, dy)]++;
            }
            for(auto [_, v] : rec) ans = max(ans, v);
            ans = max({ans, sc1, sc2});
        }
        return ans + 1;
    }
};

LeetCode-149 Max Points on a Line