"find the line that contains the maximum number of points in P"的哈希函数

Question

这是Elements of Programming Interviews书籍的段落：

让P为平面中的一组n个点。每个点都有整数 坐标。设计一种用于计算一条线的有效算法 包含p。

中的最大点数

在解决方案部分中，如下所述：

 Every pair of distinct points defines a line. We can use a hash table
H to map lines to the set of points in P that lie on them.

这是 Line的哈希函数：

// Hash function for Line.
struct HashLine {
   size_t operator()(const Line& l) const {
       return hash <int >()(l.slope.first) ^ hash <int >()(l.slope.second) ^ hash <int >()(l.intercept.first) ^ hash <int >()(l.intercept.second);
}

这是斜率和截距的声明：

 pair <int, int> get_canonical_fractional(int a, int b) {
    int gcd = GCD(abs(a), abs(b));
    a /= gcd, b /= gcd;
    return b < 0 ? make_pair(-a, -b) : make_pair(a, b);
 }
     // Line function of two points , a and b, and the equation is
     // y = x(b.y - a.y) / (b.x - a.x) + (b.x * a.y - a.x * b.y) / (b.x - a.x).
     struct Line {
     Line(const Point& a, const Point& b)
     : slope(a.x != b.x ? get_canonical_fractional(b.y - a.y, b.x - a.x) : make_pair(1, 0))
     , intercept(a.x != b.x ? get_canonical_fractional(b.x * a.y - a.x * b.y,  b.x - a.x) : make_pair(a.x, 1))
     {}
       ...
     // Store the numerator and denominator pair of slope unless the line is
     // parallel to y-axis that we store 1/0.  
     pair <int, int> slope;
     // Store the numerator and denominator pair of the y-intercept unless
     // the line is parallel to y-axis that we store the x-intercept.     
     pair <int, int> intercept;
};

但是，我们怎么知道，如果斜率和拦截对是唯一的，那么它们的XOR仍然是唯一的？

Answer 1

我们可以尝试以下简单算法：

1. 创建一个用键作为(slope, intercept)对的哈希地图，作为线路和值，作为具有相同坡度截距的行数。
2. 对于所有成对的点（O(n^2)对），计算(slope, intercept)值并增加hashmap中的相应键（在最坏的情况下，它将消耗O(n^2)内存，但是如果有很多共线点，则平均空间复杂性应该应该低）。
3. 输出线路，即在hashmap中具有最高计数的(slope, intercept)（为此，您需要遍历最坏情况下的hasmap，而hasmap将包含O(n^2)条目）。