題意

一個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')。

所以，我們將分子分母同除最大公約數即可。

注意：

代碼