Hash functions for "find a line containing the maximum number of points in P",

Question

Here is an excerpt from the book Elements of Programming Interviews:

Let P be the set of n points in the plane. Each point has an integer coordinate. Develop an efficient algorithm for computing a string that contains the maximum number of points in P.

As part of the decision, the following is said:

 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.

And here is the hash function 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);
}

And here is the tilt and intercept announcement:

 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;
};

But how do we know that if the slope and intercept pair is unique, then their xor is still unique?

Answer 1

We can try the following simple algorithm:

• - (slope, intercept) , .
• ( O(n^2)) (slope, intercept) hashmap ( O(n^2), ).
• , .. (slope, intercept), - ( hasmap, O(n^2)).