149. Max Points on a Line

[namespace-io]

class Solution {
private:

    int gcd(int x, int y){
        while(x){
            y = y % x;
            swap(x, y);
        }
        return y;
    }
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        int MAX = 0;
        for(int i = 0; i < n; i++){
            int rep = 1;
            unordered_map<string, int> m;
            for(int j = i+1; j < n; j++){ 
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];

                if(x == 0 && y == 0) rep++;
                else {
                    int g = gcd(x, y);
                    m[to_string(x / g) + "_" + to_string(y/g)]++;
                }
                
            }
            
            for(auto &p : m){
                MAX = max(MAX, p.second + rep);
            }
            
            MAX = max(MAX, rep);

        }
        
        return MAX;
    }
};

class Solution {
private:
    struct pair_hash
    {
        template<class T1, class T2>
        std::size_t operator() (const std::pair<T1, T2>& p) const
        {
            auto h1 = std::hash<T1>{}(p.first);
            auto h2 = std::hash<T2>{}(p.second);
            return h1 ^ h2;
        }
    };

 
    int gcd(int x, int y){
        if(x > y) return gcd(y, x);
        if(x == 0) return y;
        return gcd(y%x, x);
    };
    
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        int MAX = 0;
        if(n < 2) return n;
        for(int i = 0; i < n; i++){
            int rep = 0;
            unordered_map<pair<int, int>, int, pair_hash> m;
            for(int j = 0; j < n; j++){
                
                   
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];

                if(x == 0 && y == 0) rep++;
                else if(x == 0) m[{0,1}]++;
                else if(y == 0) m[{1,0}]++;
                else {
                    int g = gcd(abs(x), abs(y));
                    if(x < 0) {
                        x = -x;
                        y = -y;
                    }
                    m[{x / g, y / g}]++;
                }
                
            }
            
            for(auto &p : m){
                MAX = max(MAX, p.second + rep);
            }
            
            MAX = max(MAX, rep);

        }
        
        return MAX;
    }
};