Re: [問題] 面試問到的問題...
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間12年前 (2012/12/13 14:07)推噓2(2推 0噓 2→)留言4則, 2人參與討論串6/8 (看更多)
※ 引述《Favonia (小西風最乖了*^^*)》之銘言：
: 總而言之，如果我上個段落後半部沒有想錯的話，先考
: 慮所有垂直線，然後通過對偶在參數平面上用 Bentley-
: Ottmann 找交點。全部應該可以在 O(nlgn) 時間內完成。
Bentley-Ottmann 的時間複雜度其實是 O((n+k)*lgn)，其中 k 是交點個數。
經過對偶之後，這些直線最多出現 C(n,2) = O(nn) 個交點。
完成的時間最差是 O(nnlgn) 而不是 O(nlgn)。
事實上還有比 Bentley-Ottmann 更好的演算法：
http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf
理論上可以做到 O(nlgn + k)，在本題中也就是 O(nn)。
只是這個演算法不太容易實作，反倒是原po提出的 hashing 還比較務實。
－
接著說明一下直線截成線段的問題。
對偶的時候，點(a,b)對偶成直線y=ax+b。
考慮兩個直線的交點，也就是兩條直線解聯立方程式。
根據公式解(Cramer's rule)，
ax+by=e, cx+dy=f 這兩條直線，
其交點的x座標範圍一定會在 |e|*|d|+|b|*|f| 之內（當abcdef都是整數）。
所以我們只要設立一個足夠大與一個足夠小的x座標，再把x座標代入到直線中求得y座標，
就可以把直線截成線段，同時保留所有直線交點。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.135.22
※ 編輯: DJWS 來自: 36.225.135.22 (12/13 16:04)
※ 編輯: DJWS 來自: 36.225.135.22 (12/13 16:05)
※ 編輯: DJWS 來自: 36.225.135.22 (12/13 16:16)
推
12/13 19:12, , 1F
12/13 19:12, 1F
推
12/13 19:17, , 2F
12/13 19:17, 2F
→
12/13 19:17, , 3F
12/13 19:17, 3F
→
12/13 21:45, , 4F
12/13 21:45, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 8 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
