Leetcode 149 - Max Points on a Line（Math）

题意

一个2D平面内有若干个点，找一条直线使之穿过的点数最多，求最多穿过的点数。

思路

首先，我们先从一般情况考虑，假设我们当前直线已经穿过一个点(a,b)$(a, b)$了，那么只需要枚举剩下的点p(x,y)$p(x, y)$，并且建立map[x - a / y - b]穿过点数的映射即可。

那么，我们这道题只需要枚举直线穿过的点，然后再遍历剩下的点求斜率并且统计就好。

在求斜率的时候，假设我们当前直线起点为(a,b)$(a, b)$，穿过两个点：(x1,y1)$(x_1, y_1)$和(x2,y2)$(x_2, y_2)$。那么斜率为y2−y1x2−x1$/frac{y_2 - y_1}{x_2 - x_1}$。但是实际上会存在精度误差，比如现在leetcode数据增强了直接求斜率就不能过了。所以我们要找一个替代的方案。

假设我们斜率k=xy$k = /frac{x}{y}$，我们需要将double型的k转换成一个无精度损失的表示方法，因为k=xy$k = /frac{x}{y}$，我们只需要将分子分母约分成最简表示k=x′y′$k = /frac{x'}{y'}$，那么我们的k就可以转化成了pair<int, int>的(x', y')。

所以，我们将分子分母同除最大公约数即可。

注意：

代码