Share my C++ Solution


  • 0
    S
      int maxPoints(vector<Point>& points) {
            sort(points.begin(), points.end(), [this](Point &a, Point &b) {
                return a.x < b.x || (a.x == b.x && a.y <= b.y);
            });
            
            double eps = 1e-6;
            
            int maxPoints = 0;
            
            for(int i = 0; i < points.size(); i++) {
                int overlaps = 0;
                vector<double> slopes;
                
                double ix = points[i].x;
                double iy = points[i].y;
                
                for(int j = i + 1; j < points.size(); j++) {
                    double jx = points[j].x;
                    double jy = points[j].y;
                    
                    if(abs(ix - jx) < eps && abs(iy - jy) < eps) overlaps++;
                    else if(abs(ix - jx) < eps) slopes.push_back(INT_MAX);
                    else slopes.push_back((jy - iy) / (jx - ix));
                }
                
                sort(slopes.begin(), slopes.end());
                
                int cnt = slopes.size() > 0 ? 1 : 0;
                maxPoints = max(maxPoints, overlaps + 1 + cnt);
                
                for(int k = 1; k < slopes.size(); k++) {
                    if(abs(slopes[k] - slopes[k-1]) < eps) {
                        cnt++;
                        maxPoints = max(maxPoints, cnt + overlaps + 1);
                    } else {
                        cnt = 1;
                    }
                }
                
                i += overlaps;
            }
            
            return maxPoints;
        }

Log in to reply
 

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