最佳直线

给定一个二维平面及平面上的 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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var bestLine = function(points) {
    var inLine = function (p0, p1, p2) {
        return (p1[1] - p0[1]) * (p2[0] - p0[0]) == (p1[0] - p0[0]) * (p2[1] - p0[1])
    }

    var currentDiff, currentAppend, tempDiff, diffArr = [], diffObj = {}, max = [0, '']
    for (var i = 0; i < points.length - 1; i++) {
        for (var k = i + 1; k < points.length; k++) {
            var key = i + ',' + k
            for (var j = k + 1; j < points.length; j++) {
                if (inLine(points[i], points[k], points[j])) {
                    diffObj[key] = diffObj[key] || [i, k]
                    if (diffObj[key].indexOf(j) == -1) {
                        diffObj[key].push(j)
                        diffObj[key] = diffObj[key].sort((a, b) => a - b)
                        if (diffObj[key].length == max[0]) {
                            if (diffObj[key][0] < diffObj[max[1]][0] || (diffObj[key][0] == diffObj[max[1]][0] && diffObj[key][1] < diffObj[max[1]][1])) {
                                max[0] = diffObj[key].length
                                max[1] = key
                            }
                        } else if (diffObj[key].length > max[0]) {
                            max[0] = diffObj[key].length
                            max[1] = key
                        }
                    }
                }
            }
        }
    }
    var res = diffObj[max[1]]
    if (res && res.length > 2) {
        return res.slice(0, 2)
    } else {
        return [0, 1]
    }
};