C++刷leetcode（面试题 16.14. 最佳直线）【数学】

糖逗

题目描述：

给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。

设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。

示例：

输入： [[0,0],[1,1],[1,0],[2,0]]
输出： [0,2]
解释： 所求直线穿过的3个点的编号为[0,2,3]
提示：

2 <= len(Points) <= 300
len(Points[i]) = 2

class Solution {
public:
    vector<int> bestLine(vector<vector<int>>& points) {
        vector<int>res(2);
        int len = points.size();
        int max_len = 0;
        for(int i = 0; i < len-1; i++){
            map<double, vector<int> >store;
            double max_temp = 0;
            for(int j = i+1; j < len; j++){
                double temp;
                if(points[i][1] - points[j][1] == 0){
                    temp = 0.0;

                }else if(points[i][0] - points[j][0] == 0){
                    temp = (double)INT_MAX;

                }else{
                    temp = (points[i][1] - points[j][1]) / (double)(points[i][0] - points[j][0]);
                }
                store[temp].push_back(j);
                if(store[temp].size() > max_len){
                    if(store[temp].size() >= 1){
                        res[0] = i;
                        res[1] = store[temp][0];
                    }
                    max_len = store[temp].size();
                    max_temp = temp;
                }
            }
        }
        return res;
    }
};

注意事项：直线斜率计算。

糖逗