推 suhorng:這樣做是 O(n^3) 喔, 計算出現次數要 n 12/11 22:37
→ wangtrying:big O的話, n會被n^2蓋掉吧? 還是我有誤會你的意思? 12/11 22:46
→ suhorng:找出最多點共線時線上的點數 所以位置不同 斜率相同的線 12/11 22:48
→ suhorng:是不同的 12/11 22:48
→ suhorng:所以粗估每個斜率有 n 種可能(n個點) 當然可能少於這數字 12/11 22:48
→ wangtrying:ㄟ 不好意思 我可能沒有把題目敘述得很好...orz 12/11 22:51
→ wangtrying:我印象中他的意思應該是說 比如說 灑兩個點在平面上 12/11 22:52
→ wangtrying:那得到的值當然是2, 灑三個點, 而這三個點形成三角形 12/11 22:53
→ wangtrying:那也是2, 但是說這三個點剛好共線的話, 那就是3了 12/11 22:53
→ wangtrying:然後現在撒了n個點在平面上, 假如恰好有四點共線 12/11 22:55
→ wangtrying:那就是4, 大概是這樣啦... 12/11 22:55
推 suhorng:可以考慮這樣：現在 x=0 的線上有 10 個點 12/11 22:56
→ suhorng:x=1 的線上有 11 個點 12/11 22:56
→ suhorng:x=2 的線上有 13 個點 12/11 22:56
→ suhorng:那計算共線時 x=0, x=1, x=2 這三條鉛直線不會只算一次 12/11 22:58
→ suhorng:或者說 斜率一樣不代表他們貢獻 12/11 22:59
→ suhorng: 共線 12/11 22:59
→ wangtrying:阿 我懂了 感謝suhorng大大 Y=mX+b, m跟b都要算出來 12/11 23:02
推 wtvwtvwtv200:最快的做法應該是依序固定一個點，計算其他所有點 12/11 23:03
→ wtvwtvwtv200:跟該點的斜率，然後用hash加速統計，O(n^2) 12/11 23:04
→ wangtrying:斜率是不夠的, 以suhorng大大的例子來說, 正確答案是13 12/11 23:06
→ wangtrying:但是只算斜率的話 會得到34 就錯了 12/11 23:06
→ wangtrying:所以應該要用<m,b>的tuple當key, 丟到hash裡面 12/11 23:08
推 suhorng:hash是對的 就是枚舉點然後轉一圈 12/11 23:08
→ suhorng:然後相對於這個點斜率相同的就是在同條線上 12/11 23:09
→ wtvwtvwtv200:姆…我的意思是針對每個點分別計算跟其他點的斜率 12/11 23:09
→ wangtrying:感謝wtvwtvwtv200跟suhorng兩位大大 orz 12/11 23:09
→ suhorng:看到推文了XD 差不多例子 12/11 23:09
→ wangtrying:wtv大 的意思是說 每轉一圈就紀錄斜率出現次數的最大值 12/11 23:13
→ wangtrying:這樣好像比較漂亮喔 12/11 23:14
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: wangtrying (114.24.44.237), 時間: 12/13/2012 00:12:34
→ wtvwtvwtv200:＂轉一圈＂這個形容不太對，因為要排序的話 12/13 00:28
→ wtvwtvwtv200:複雜度會變成O(n^2logn)，用hash不管順序直接掃O(n2) 12/13 00:29