c++ solution considering a issue which float point as key of map


  • 0
    D

    A number of solutions using float/double as the key of the map. This will introduce precision issue issue.
    The following solution fix this bug.
    Inspired from http://www.cnblogs.com/grandyang/p/4579693.html

    private:
        int gcd(int a, int b){
            return (b==0) ? a : gcd(b, a%b);
        }    
    public:
        int maxPoints(vector<Point>& points) {
            
            int n = points.size();
            int ret = 0;
            if(n <= 2) return n;
            
            for(int i = 0; i < n; ++i){
                map<pair<int,int>,int> mp;
                Point pi = points[i];
                int same = 1;
                
                for(int j = i + 1; j < n; ++j){
                    
                    Point pj = points[j];
                    if(pj.x == pi.x && pj.y == pi.y){                   
                            same++;
                    }else{
                        //double slope = double(pj.y - pi.y)/double(pj.x-pi.x);
                        int dx = pj.x - pi.x;
                        int dy = pj.y - pi.y;
                        int d = gcd(dx, dy);
                        ++mp[pair<int,int>(dx/d,dy/d)];
                    }
                    
                }
                
                int local_max = 0;
                for (auto it = mp.begin(); it != mp.end(); ++it){
                    local_max = max(it->second, local_max);
                }
                local_max += same;
                ret = max(ret, local_max);
                
            }
            return ret;
                  
        }
    

Log in to reply
 

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