※ 引述《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?