作者Favonia (小西风最乖了*^^*)
站内Prob_Solve
标题Re: [问题] 面试问到的问题...
时间Thu Dec 13 11:42:02 2012
※ 引述《Leon (Achilles)》之铭言：
: 你下面提出的 Bentley-Ottmann, 我不熟悉
: 所以我去看了一下. 这似乎试用在 line segment.
: 如果用 duality 变换, 出来的应该为 line, 而不是 line segment.
: 在这个情况下, 要怎麽改?
我是初次看到这题目，还请网友帮忙验证。
可以想像只要取够长的线段就好了，因为无穷远的交点已经
先处理掉（也就是平行线）。因为没有垂直线，可以想像在很远
的地方会按照斜率排序。因此我们就按照斜率排序，算出斜率相
邻的直线到多远以後就不会交叉。同斜率的平行线要当一组来处
理就是了。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.39