给定一个二维平面及平面上的 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
1.暴力，遍历所有2个点可能组成的直线，再对每条直线得到最终的答案，一个小技巧是如何解决相同点的问题，这里我们维护一个变量记录下点的多少
2.一个巧妙的方式，需要观察到所有在一条直线上的点的k和b是一样的
class Solution: def bestLine(self, points: List[List[int]]) -> List[int]: res=[] c=0 for i in range(len(points)): for j in range(len(points)): if i!=j: cnt=0 t=[] for k in range(len(points)): if (points[j][1]-points[i][1])*(points[k][0]-points[i][0])==(points[k][1]-points[i][1])*(points[j][0]-points[i][0]): cnt+=1 if len(t)<2: t.append(k) if cnt==c: c=cnt res.append(t) elif cnt>c: c=cnt res=[t] res.sort() return res[0] class Solution: def bestLine(self, points: List[List[int]]) -> List[int]: d = {} x = y = 0 maxCount = 0 for i in range(len(points)): for j in range(i+1, len(points)): k, b = self.f([points[i], points[j]]) if (k, b) in d.keys(): d[(k, b)][0] += 1 else: d[(k, b)] = [1, (i, j)] if d[(k, b)][0] > maxCount or (d[(k, b)][0] == maxCount and d[(k, b)][1][0] < x) or (d[(k, b)][0] == maxCount and d[(k, b)][1][0] == x and d[(k, b)][1][1] < y): maxCount = d[(k, b)][0] x, y = d[(k, b)][1] #print(x, y) return [x, y] # 求两点之间连线的斜率k和截距b def f(self, points: List[List[int]]) -> List[int]: if points[0][0] == points[1][0]: return [float('inf'), points[0][0]] else: return [(points[1][1]-points[0][1]) / (points[1][0]-points[0][0]), (points[0][1]*points[1][0]-points[1][1]*points[0][0]) / (points[1][0]-points[0][0])]
