C++ easy to understand solution

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

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