C++ O(n^2) solution


  • 0
    Z
    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            
            int n = points.size();
            if(n<=2) return n;
            
            map<pair<int, int>, int> lines;
            int result = 0;
            
            for(int i=0; i<n-1; i++){
                int overlap = 0;
                int localmax = 0;
                for(int j=i+1; j<n; j++){
                    
                    int a = points[j].x-points[i].x;
                    int b = points[j].y-points[i].y;
                    if(a==0 && b==0){
                        overlap++;
                        continue;
                    } 
                    
                    int gcd = GCD(a,b);
                    a /= gcd;
                    b /= gcd;
                    
                    if(lines.find(pair<int,int>(a,b))==lines.end()) 
                        lines.insert(pair<pair<int,int>,int>(pair<int,int>(a,b),1));
                    else lines[pair<int,int>(a,b)]++;
                    
                    localmax = max(localmax,lines[pair<int,int>(a,b)]);
                }
                
                result = max(result, localmax+overlap+1);
                
                if(result > n/2) return result;
                lines.clear();
            }
            return result;
        }
        
    private:
        int GCD(int a, int b){
            if(b==0) return a;
            else return GCD(b, a%b);
        }
    };
    

Log in to reply
 

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