C++_AC_Using map


  • 0

    For each two nodes, if third point and one of them have the same slope as the other two, these points are on the same line.
    We should consider: infinity slope, duplicate points.

    class Solution {
    public:
    int maxPoints(vector<Point>& points) {
        if(points.size() < 3) return points.size();
        //unordered_map<double, int> mp;
        int res = 0;
        for(int i = 0; i < points.size(); ++i){
            unordered_map<double, int> mp;
            int duplicate = 0;
            double slope = 0.0;
            for(int j = 0; j < points.size(); ++j){
                int dy = points[i].y - points[j].y;
                int dx = points[i].x - points[j].x;
                if(dy == 0 && dx == 0){duplicate++; continue;}
                if(dx != 0){
                    slope = dy*1.0/dx;
                }else{
                    slope = INT_MAX;
                }
                mp[slope]++;
            }
            
            if(mp.size() == 0){res = duplicate;}
            else{
                for(auto slope : mp){
                res = max(res, slope.second + duplicate);
                }
            }
        }
        return res;
    }
    };

Log in to reply
 

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