斜率哈希+欧几里得：平面点集共线检测算法

斜率哈希+欧几里得：平面点集共线检测算法

同一直线上的点集相关问题，使用哈希表遍历的方法，外层循环选定一个点，从头到尾去遍历其余的点，查看有多少的点与给定点的直线斜率相同（我们知道，一个点和一个斜率可以确定一条直线），那么只需要在哈希表记录下内层循环遍历下同一斜率的点，最后加上定点就得到当前组合下的最大点数。
斜率一共对应五种情况：
横纵坐标差值为0是特殊情况处理，直接给特定斜率

1. 横坐标差值为0 （字符串“ 1/ 0” 表示）
2. 纵坐标差值为0 （字符串“ 0 / 1 “表示）
3. 横纵差值都为正 （斜率为正）
4. 横纵差值都为负 （斜率为正）
5. 横纵差值有一个为负一个为正 （斜率为负，并且-1 /2 和 1 / -2 都要统一为-1 /2 ）
   最终把斜率转换为字符串存储，先使用欧几里得算法来缩放差值diff_x和diff_y，得到一个最简斜率（需要为负数斜率加”-“）作为哈希表的key

class Solution {
public:
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
    int maxPoints(vector<vector<int>>& points) {
        if (points.size() == 1) {
            return 1;
        }
        int res = INT_MIN;
        for (int i = 0; i < points.size(); i++) {
            unordered_map<string, int> lineMap;
            int resV = INT_MIN;
            for (int j = i + 1; j < points.size(); j++) {
                int diff_x = points[i][0] - points[j][0];
                int diff_y = points[i][1] - points[j][1];
                
                int g = gcd(abs(diff_x), abs(diff_y));
                int shrink_x = 0;
                int shrink_y = 0;
                if(diff_x == 0){
                   shrink_x = 1;
                   shrink_y = 0;
                }else if(diff_y == 0){
                   shrink_x = 0;
                   shrink_y = 1;
                }else{
                   shrink_x = diff_x / g;
                   shrink_y = diff_y /g;
                }
                string lineRate = "";
                
                lineRate += to_string(abs(shrink_x));
                lineRate.push_back('_');
                lineRate += to_string(abs(shrink_y));
                 if(shrink_x < 0 && shrink_y > 0|| shrink_x > 0 && shrink_y < 0){
                   lineRate = "-"+lineRate;
                }
                lineMap[lineRate]++;
                resV = max(lineMap[lineRate], resV);
            }
            res = max(res, resV + 1);
        }
        return res;
    }
};

欧几里得算法：（递归写法，当一个参数为0时，自动返回另一个非零参数）

int gcd(int a,int b){
    return b == 0 ? a : gcd(b,a%b);
}