In linear algebra, two different points defines a line, `y = ax + b`

, to be more general to consider vertical line which can be represented using `x = c`

, I use the following representation for line: `by = ax + c`

.

Map `stats`

is created to record the straight lines with count of points on it. For easy understanding, I converted `by = ax + c`

into a string as map's key value: `"by=ax+c"`

, e.g. `"2y=3x+0"`

, and its value is number of points on that line accordingly.

However, how about two points that are the same? It's valid for the test cases, so I decided to preprocess the points using a frequency map, let it be `freq`

to store the unique points with frequency.

Then iterate through map `freq`

, outer loop pointer `it1`

starts from the 2nd point till the last point, the inner loop pointer `it2`

is basically iterating through each point before `it1`

in `freq`

. If `it1`

and `it2`

defines a line that already exists in stats, simply add count of `it1`

in `freq`

map to line; Otherwise, `it1`

and `it2`

identifies a new line, update the `stats`

map accordingly. One thing to note, in the inner loop, `(it1, it2)`

and `(it1, it2')`

may actually define the same line, so as to avoid adding the count of it1 to the same line more than once, I use a set `visit`

to record lines that have already counted `it1`

, and `visit`

needs to be reset for each outer loop pointer `it1`

.

```
class Solution {
public:
int maxPoints(vector<Point>& points) {
if(points.size() <= 2) return (int)points.size();
unordered_map<string, int> stats;
map<pair<int, int>, int> freq;
unordered_set<string> visited;
for(auto p: points){
freq[make_pair(p.x, p.y)]++;
}
int ans = freq.begin()->second;
for(auto it1 = ++freq.begin(); it1 != freq.end(); ++it1){
visited.clear();
for(auto it2 = freq.begin(); it2 != it1; ++it2){
int deltaX = it1->first.first - it2->first.first;
int deltaY = it1->first.second - it2->first.second;
int d = gcd(deltaX, deltaY);
int a = d ? deltaY / d : 1;
int b = d ? deltaX / d : 0;
int c = b * (it1->first.second) - a * (it1->first.first);
string line = to_string(b) + "y=" + to_string(a) + "x+" + to_string(c);
if(stats.find(line) == stats.end()){
stats[line] = it1->second + it2->second;
visited.insert(line);
}else {
if(visited.find(line) == visited.end()){
stats[line] += it1->second;
visited.insert(line);
}
}
ans = max(ans, stats[line]);
}
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
};
```