Avoid using double as key by a custom hasher

  • 0

    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 {
        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 {
                        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.