class Solution {
public:
int maxPoints(vector<Point>& points) {
int n = (int)points.size();
unordered_map<float, int> map;
int res = 0;
for(int i = 0; i < n; i++){
int same = 1;
int vertical = 0;
int tmp = 0;
map.clear();
for(int j = i + 1; j < n; j++){
Point a = points[i];
Point b = points[j];
if(a.x == b.x){
if(a.y != b.y){
vertical++;
}
else{
same++;
}
}
else{
tmp = max(++map[(float)(b.y  a.y) / (b.x  a.x)], tmp);
}
}
res = max(res, same + max(vertical, tmp));
}
return res;
}
};
16ms c++ easy understanding solution


Solution fails below test. It's unsafe to use
float
/double
as keys.Submission Result: Wrong Answer Input: [[0,0],[94911151,94911150],[94911152,94911151]] Output: 3 Expected: 2
One possible solution is to encode slopes as strings
int rise = p2.y  p1.y; int run = p2.x  p1.x; int g = gcd(rise, run); string slope = to_string(rise/g) + "," + to_string(run/g);
