```
class Solution {
int gcd(int a, int b) {
if (b!=0) {
return gcd(b, a%b);
} else {
return a;
}
}
public:
int maxPoints(vector<Point>& points) {
if (points.size()<3) {
return points.size();
}
int maxCount = 0;
for (auto p1 : points) {
unordered_map<string, int> counts;
int maxNoOriginPoints = 0; // we are calcuating the non-origin points on the same slope based on the "shifted" origin of p1
for(auto p2 : points) {
int dy = p2.y - p1.y;
int dx = p2.x - p1.x;
int sign = dy*dx >=0 ? 1 : -1;
dy = abs(dy);
dx = abs(dx);
int g = gcd(dy, dx);
dy = g == 0 ? dy : dy/g;
dx = g == 0 ? dx : dx/g;
string key = sign==-1 ? "-":"+";
key +=std::to_string(dx) + "_" + std::to_string(dy);
counts[key]++;
if (dx==0 && dy==0) {
continue;
}
maxNoOriginPoints = max(maxNoOriginPoints, counts[key]);
}
maxCount = max(maxCount, maxNoOriginPoints + counts["+0_0"]); // for all connected points on the same line, we should add back the "origin" if it exists, which is the p1 above. e.g for (0,0) and (1,1), there should be 2 points on the same line
}
return maxCount;
}
};
```