My O(n^2) solution in C++ with self-defined equal and hash function


  • 1
    Y

    I try to avoid compare double as machine error may lead to catastrophic result.

    #include <iostream>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    #include <utility>
    
    using namespace std;
    
    struct Point{
        int x;
        int y;
        Point() : x(0), y(0) {}
        Point(int a, int b) : x(a), y(b) {}
    };
    
    // Equal function for Point struct
    bool operator==(const Point &p1, const Point &p2){
        return p1.x == p2.x && p1.y == p2.y;
    }
    
    // HashCode fuction for Point struct
    struct hashPoint{
        size_t operator()(const Point &point) const{
            hash<int> tmp;
            return tmp(point.x) ^ (tmp(point.y) << 1);
        }
    };
    
    // Find the greatest common division for two integers,
    // useful in building a Line struct
    int gcd(int x, int y){
        if (x < y) return gcd(y, x);
        if (y < 0) return gcd(x, -y);
        if (y == 0) return x;
        return gcd(y, x%y);
    }
    
    struct Line{
        // Formula: a * x + b * y = c
        int a;
        int b;
        int c;
        
        // Make sure that the same line in 2D space will have the same expression
        Line(int _a, int _b, int _c){
            a = _a; b = _b; c = _c;
            if (a < 0){
                a = -a; b = -b; c = -c;
            }
            if (a == 0){
                c = c / b; b = 1; return;
            }
            int max = gcd(a, b);
            a = a / max; b = b / max; c = c / max;
        }
    };
    
    // Equal function for Line struct
    bool operator==(const Line &l1, const Line &l2){
        return l1.a == l2.a && l1.b == l2.b && l1.c == l2.c;
    }
    
    // Hash function for Line struct
    struct hashLine{
        size_t operator()(const Line &line) const{
            hash<int> tmp;
            return tmp(line.a) ^ (tmp(line.b) << 1) ^ (tmp(line.c) << 2);
        }
    };
    
    class Solution {
    public:
        int maxPoints(vector<Point> &points) {
            
            if (points.size() == 0){
                return 0;
            }
            
            // hashMap to keep all points and their counts
            unordered_map<Point, int, hashPoint> record;
            
            typedef pair<unordered_set<Point, hashPoint>, int> pSet;
            
            // hashMap to keep all lines, their component points and counts of points.
            unordered_map<Line, pSet, hashLine> lineMap;
            for (Point pt : points) {
                if (record.find(pt) == record.end()) {
                    record[pt] = 1;
                }else{
                    record[pt] ++;
                }
            }
            
            if (record.size() == 1) {
                return record.begin()->second;
            }
            
            // Search all possible lines
            for (auto iter = record.begin(); iter != record.end(); iter ++) {
                auto iter2 = iter;
                for (iter2 ++; iter2 != record.end(); iter2 ++) {
                    int x1 = iter->first.x, x2 = iter2->first.x;
                    int y1 = iter->first.y, y2 = iter2->first.y;
                    // Build a line with two given points.
                    Line line(y2 - y1, x1 - x2, x2 * y1 - x1 * y2);
                    if (lineMap.find(line) == lineMap.end()) {
                        // If this is a new line.
                        pSet tmp;
                        tmp.first.insert(iter->first);
                        tmp.first.insert(iter2->first);
                        tmp.second = iter->second + iter2->second;
                        lineMap[line] = tmp;
                    }else{
                        // If this line already exist, check if the second point is added.
                        // If not, add it.
                        // No need to check the first point.
                        // It should be added because it can be scanned before as the line already exist.
                        if (lineMap[line].first.find(iter2->first) == lineMap[line].first.end()) {
                            lineMap[line].first.insert(iter2->first);
                            lineMap[line].second += iter2->second;
                        }
                    }
                }
            }
            
            // Find the maximum, return it.
            int max = 2;
            for (auto iter = lineMap.begin(); iter != lineMap.end(); iter ++) {
                if (max < iter->second.second) {
                    max = iter->second.second;
                }
            }
            
            return max;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.