※ 引述《DJWS (...)》之銘言：
: ※ 引述《Favonia (小西風最乖了*^^*)》之銘言：
: : 總而言之，如果我上個段落後半部沒有想錯的話，先考
: : 慮所有垂直線，然後通過對偶在參數平面上用 Bentley-
: : Ottmann 找交點。全部應該可以在 O(nlgn) 時間內完成。
: Bentley-Ottmann 的時間複雜度其實是 O((n+k)*logn)，其中 k 是交點個數。
: 經過對偶之後，這些直線最多出現 C(n,2) = O(n^2) 個交點。
: 完成的時間最差是 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。
: 考慮兩個直線的交點，也就是兩條直線解聯立方程式。
: 根據公式解，交點的座標範圍一定會在 |a|*|b|+|c|*|d| 之內。
First, I don't understant your notation.
What do you mean by the range |a|*|b|+|c|*|d| ?
It seems not a range in 2D ?
And I have the same question for you.
Assume you have N lines, based on your description
You claim there is a range for the intersection.
Then, how many operations you need to calculate the range?