Slower but quite readable C++


  • 0
    P

    Instead of calculating slopes, which is popular, I stored the normal vector of the line equations instead to avoid potential floating point precision problems.
    The solution is more object-oriented and easier to understand. It tends to be slower due to the lack of compiler optimization. With -O3, this should be much faster.

    #include <map>
    #include <set>
    
    using namespace std;
    
    inline int gcd(int m, int n) {
        if(n == 0)
            return m;
        return gcd(n, m % n);
    }
    
    inline bool operator < (const Point& p1, const Point& p2) {
        if(p1.x == p2.x)
            return p1.y < p2.y;
        return p1.x < p2.x;
    }
    
    struct Line {
        int a, b, c;
        Line():a(0), b(0), c(0) {}
        Line(const Line& other): a(other.a), b(other.b), c(other.c) {}
        Line(int _a = 0, int _b = 0, int _c = 0):a(_a), b(_b), c(_c) {
        }
        Line(Point& p1, Point& p2) { // solve the equation
            int dx = p1.x - p2.x;
            int dy = p1.y - p2.y;
            a = dy;
            b = -dx;
            if(a < 0) {
                a = -a;
                b = -b;
            }
            int g = gcd(abs(a), abs(b));
            if(g > 0) {
                a /= g;
                b /= g;
            }
            c = a * p1.x + b * p1.y;
        }
    
        inline bool isValid() const {
            return (a != 0 || b != 0);
        }
    
        inline bool operator < (const Line& l) const {
            if(c == l.c) {
                if(a == l.a) {
                    return b < l.b;
                }
                return a < l.a;
            }
            return c < l.c;
        }
    };
    
    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            if(points.empty())
                return 0;
            if(points.size() <= 2)
                return points.size();
            int max_cnt = 0;
            map<Line, set<int>> lines;
            // every two points can form a straight line
            for(int i = 0; i < points.size(); ++i) {
                for(int j = i + 1; j < points.size(); ++j) {
                    Point& p1 = points[i];
                    Point& p2 = points[j];
                    Line line(p1, p2);
                    if(!line.isValid())
                        continue;
                    auto& line_points = lines[line];
                    line_points.insert(i);
                    line_points.insert(j);
                    if(line_points.size() > max_cnt)
                        max_cnt = line_points.size();
                }
            }
            if(max_cnt == 0) // no valid lines were found, all points are the same
                max_cnt = points.size();
            return max_cnt;
        }
    };
    

Log in to reply
 

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