8ms c++ solution


  • 0
    D

    I am using a vector with pre-assigned spaces to store slopes.

    /**
     * Definition for a point.
     * struct Point {
     *     int x;
     *     int y;
     *     Point() : x(0), y(0) {}
     *     Point(int a, int b) : x(a), y(b) {}
     * };
     */
    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            int result = 0;
            vector<double> slopes(points.size());
            for (int i = 0; i < points.size(); i++) {
                int cnt_same_x = 1, cnt_same = 1;  // including itself
                int k = 0;  // number of nodes not in the same vertical line
                for (int j = i + 1; j < points.size(); j++) {
                    int dx = points[i].x - points[j].x, dy = points[i].y - points[j].y;
                    if (dx == 0) {cnt_same_x++; cnt_same+=(dy==0); continue;}
                    slopes[k++] = 1.0*dy/dx;
                }
                result = max(result, cnt_same_x);
                sort(slopes.begin(), slopes.begin() + k);
                for (int j1 = 0, j2 = 0; j1 < k; j1 = j2) {
                    while (j2 < k && fabs(slopes[j1]-slopes[j2]) < 1e-5) j2++;
                    result = max(result, j2 - j1 + cnt_same);
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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