在 XY 平面上,
給n個點 Pi = (Xi, Yi), i = 1...n,
找出最多點共線時 這條線上面的點的個數
怎麼解的漂亮啊?
小弟想得到的就是暴力法
每兩個點算斜率 m
放到一個Dictionary的資料結構
key是m, value是出現次數...
所以 總共會計算 n(n-1)/2 次 m 值
然後再對Dictionary的value找最大值 就是解了
但是這樣是O(n^2) 不知道大家有沒有更好的做法?

這樣做是 O(n^3) 喔, 計算出現次數要 n

big O的話, n會被n^2蓋掉吧? 還是我有誤會你的意思?

找出最多點共線時線上的點數 所以位置不同 斜率相同的線是不同的所以粗估每個斜率有 n 種可能(n個點) 當然可能少於這數字

ㄟ 不好意思 我可能沒有把題目敘述得很好...orz我印象中他的意思應該是說 比如說 灑兩個點在平面上那得到的值當然是2, 灑三個點, 而這三個點形成三角形那也是2, 但是說這三個點剛好共線的話, 那就是3了然後現在撒了n個點在平面上, 假如恰好有四點共線那就是4, 大概是這樣啦...

可以考慮這樣：現在 x=0 的線上有 10 個點x=1 的線上有 11 個點x=2 的線上有 13 個點那計算共線時 x=0, x=1, x=2 這三條鉛直線不會只算一次或者說 斜率一樣不代表他們貢獻共線

阿 我懂了 感謝suhorng大大 Y=mX+b, m跟b都要算出來

最快的做法應該是依序固定一個點，計算其他所有點跟該點的斜率，然後用hash加速統計，O(n^2)

斜率是不夠的, 以suhorng大大的例子來說, 正確答案是13但是只算斜率的話 會得到34 就錯了所以應該要用<m,b>的tuple當key, 丟到hash裡面

hash是對的 就是枚舉點然後轉一圈然後相對於這個點斜率相同的就是在同條線上

姆…我的意思是針對每個點分別計算跟其他點的斜率

感謝wtvwtvwtv200跟suhorng兩位大大 orz

看到推文了XD 差不多例子

wtv大 的意思是說 每轉一圈就紀錄斜率出現次數的最大值這樣好像比較漂亮喔