# Slower but quite readable C++

• 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;
}
};
``````

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