N <= 200000乍看之下可能覺得要找到直線太困難,但是因為題目有保證"最多點的那條直線上有超過 N/4 個點",我們有很大的機率可以找到那條線
以下稱最多點的線為L
怎麼找呢? 我們找兩個點,然後跟其他所有點比較,看其他點有沒有跟這兩個點共線
因為保證超過N/4個點,所以任意選兩點且都在L上的機率為1/16。
1/16的機率聽起來很低,但是如果我們找很多次,至少中一次的機率就會變高
舉例來說,我們隨機找了30組的點,且這30組都不在L上的機率為 1 - (15/16)30 = 0.85 找到的機率為85% 這可能還不夠
找50組找到L的機率就有96%,找100組找到L的機率有99.8%
要如何判斷三個點有沒有共線呢? 最簡單的就是delta_x1, delta_y1 跟delta_x2, delta_y2成比例 也可以用向量
整體時間複雜度:O(N)
影片:https://youtu.be/0r2D32esF3Y?t=334