题解 | 穿点最多的直线

/*
struct Point {
    int x;
    int y;
    Point() :
            x(0), y(0) {
    }
    Point(int xx, int yy) {
        x = xx;
        y = yy;
    }
};*/
#include <cstddef>
#include <cstdint>
#include <functional>
#include <unordered_map>
#include <utility>
#include <vector>
class DenseLine {
    struct Line {
        double k, b;
        bool operator==(const Line& other) const {
            return std::abs(k - other.k) < 1e-9 && std::abs(b - other.b) < 1e-9;
        };
    };
    struct LineHash {
        size_t operator()(const Line& l) const {
            auto k_bucket = static_cast<int64_t>(l.k * 1e9);
            auto b_bucket = static_cast<int64_t>(l.b * 1e9);
            return hash<int64_t>()(k_bucket) ^ hash<int64_t>()(b_bucket);
        }
    };

  public:
    vector<double> getLine(vector<Point> p, int n) {
        // write code here
        unordered_map<Line, int, LineHash> lines;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                double k = (p[j].y - p[i].y)*1.0 / (p[j].x - p[i].x );
                double b = p[i].y - k * p[i].x;
                lines[Line{k, b}]++;
            }
        int count = 0;
        Line res;
        for (auto l : lines) {
            if (l.second > count) {
                count = l.second;
                res = l.first;
            }
        }
        return {res.k, res.b};


    }
};