Leetcode149 - maximum number of points on a line - Math - hash table

Original link

Note：

Enumerate all points , Let him be the origin

After selecting the origin , Find all the points again , There are three situations at this time
1、 The point coincident with the current origin （ It can be regarded as the point above the straight line with arbitrary slope ）
2、 A point on a vertical line （ At this time, the slope can't be calculated , The divisor cannot be zero 0）
3、 Normal point , The point that forms a straight line with a slope

Then each point is classified according to the slope , Finally, first check the number of points with normal slope and points on the vertical line
And then look at answer and More points after this traversal + The point of coincidence Who is more

On the second traversal , There must be a coincidence point , Is the current point , This is not a repetition ？
It is only counted during the second traversal , Not much

The code is as follows ：

class Solution {
    
public:
    int maxPoints(vector<vector<int>>& points) {
    
        int ans = 0;
        for(auto& p: points){
    
            int s = 0, v = 0;
            unordered_map<long double, int> cnt;
            for(auto& q : points){
    
                if(p == q)    s ++;
                else if(p[0] == q[0])   v ++;
                else{
    
                    long double k = (long double) (q[1] - p[1]) / (q[0] - p[0]);
                    cnt[k] ++;
                }
            }
            int c = v;
            for(auto [k, v] : cnt)  c = max(c, v);
            ans = max(ans, c + s);
        }
        return ans;
    }
};