#26928: AC率低 來寫個解題報告好了


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 :
2024-04-13 22:06:23
g051. 最多點的線 | From: [111.243.18.144] | 發表日期 : 2021-09-02 17:58

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

 
ZeroJudge Forum