Avoid using double as key by a custom hasher


  • 0
    M

    I just found that in my previous submission I used unordered_map<double, int> in which the key is the slope of lines. I think comparing double for equality is bad practice so I write a Line class and use it as the key. To be able to use Line as key I overwrite the operator== in the Line class and I write a custom hasher for the Line class. Here is the code.

    struct Line {
        Line(const Point& a, const Point& b, double eps=1e-7) {
            epsilon = eps;
            isSamePoint = false;
            isSlopeVertical = false;
            slope = 0;
            
            if(a.x == b.x && a.y==b.y) isSamePoint = true;
            else if(a.x == b.x) isSlopeVertical = true;
            else slope = double(a.y-b.y)/double(a.x-b.x);
        }
        
        bool operator==(const Line& other) const {
            return fabs(slope-other.slope) < epsilon;
        } 
    
        double epsilon;
        double slope;
        bool isSlopeVertical;
        bool isSamePoint;
    };
    
    struct LineHasher {
        size_t operator()(const Line& l) const {
            return hash<double>()(l.slope);
        }
    };
     
    class Solution {
    public:
        int maxPoints(vector<Point> &points) {
            if(points.size() <= 2) return points.size();
            
            int globalMax = 0;
            for(int i=0; i<points.size()-1; i++) {
                unordered_map<Line,int,LineHasher> map;
                int samePoint = 0, vertical = 0, localMax = 0;
                for(int j=i+1; j<points.size(); j++) {
                    Line l(points[i],points[j]);
                    if(l.isSamePoint) samePoint++;
                    else if(l.isSlopeVertical) vertical++;
                    else {
                        map[l]++;
                        localMax = max(localMax,map[l]);
                    }
                }
                localMax = max(localMax,vertical);
                localMax += (samePoint + 1);
                globalMax = max(globalMax,localMax);
            }
            return globalMax;
        }
    };

Log in to reply
 

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