Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
第一反應(yīng)卒煞，先畫圖看看是個啥規(guī)律荔燎。人類是怎么判斷點和線的灼卢。
如下圖，用線連起來的3個點是max number of points lie on same line. 其他當(dāng)然還可以造不同的line央碟，但是數(shù)量都是2，或者1.?
所以難到我們要畫出所有的線嗎均函，這個是不是有點瞎亿虽。所以在不考慮代碼的情況下，人是怎么可以一眼看出哪條線包含最多的points的苞也。
嘗試了一下發(fā)現(xiàn)洛勉， 當(dāng)點數(shù)非常多的時候，人是無法做這個題的如迟。
窮舉收毫。 對每個點都計算一下該點和其他點連線的斜率攻走。這樣對于這個點來說，相同斜率的直線有多少條此再，就代表有多少個點在同一條直線上昔搂。 因為這些直線是相同的。另外输拇，如果計算過A, B的直線巩趁，當(dāng)計算到B時，就不用和A連線了淳附。 我們用哈希表议慰，以斜率為key，記錄有多少重復(fù)直線Ｅ铩１鸢肌！
我們用到gcd 的原因是洽糟，同一條線上的delta x, delta y都是存在一個ratio的, which is the slope炉菲。我們除了這個slope讓其變?yōu)榛綾ase。
