# My C++ solution without using hash table and accepted

• ``````class compare_points {
public:
bool operator()(const Point& p1, const Point& p2) {
if (p1.x < p2.x)
return true;
else if (p1.x == p2.x && p1.y < p2.y)
return true;
return false;
}
};
class Solution {
bool isOneLine(const Point& p1, const Point& p2, const Point& p3) {
if ((p2.y - p1.y)*(p3.x - p1.x) == (p3.y - p1.y)*(p2.x - p1.x)) {
if ((p2.y - p1.y) == 0 && (p3.y - p1.y) == 0)
return true;
if ((p3.x - p1.x) == 0 && (p2.x - p1.x) == 0)
return true;
if ((p2.y - p1.y) != 0 && (p3.y - p1.y) != 0 &&
(p3.x - p1.x) != 0 && (p2.x - p1.x) != 0)
return true;
}
return false;
}
bool equalPoint(const Point& p1, const Point& p2) {
return p1.x == p2.x && p1.y == p2.y;
}

public:
int maxPoints(vector<Point>& points) {
if (points.size() < 3)
return points.size();

sort(points.begin(), points.end(), compare_points());
int maxPoint = -1;
for (int i = 0; i < points.size()-2; ++i) {
int samePointCount = 0;
for (int j = i+1; j < points.size()-1; ++j) {
if (equalPoint(points[i], points[j])) {
samePointCount ++;
continue;
}

int current_point_numbers = 2;
for (int k = j+1; k < points.size(); ++k) {
if (isOneLine(points[i], points[j], points[k])) {
current_point_numbers ++;
}
}
current_point_numbers += samePointCount;
if (current_point_numbers > maxPoint) {
maxPoint = current_point_numbers;
}
}
}
if (maxPoint == -1) {
return points.size();
}
maxPoint = maxPoint > points.size() ? points.size() : maxPoint;
return maxPoint;
}
};
``````

• So the trade-off here is to use `O(n^3)`time in exchange of `O(1)`space usage, right?

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