※ 引述《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座标，
就可以把直线截成线段，同时保留所有直线交点。