※ 引述《FRAXIS (喔喔)》之铭言:
: 我在网络上看到一个问题:
: 给定n条垂直的线段,设计一个线性的算法找出是否存在一条直线,
: 使得此直线与此n条线段都相交。
: 我的解法是基于二维线性规划,感觉是比较不直接的方法。
: 有没有比较直接的方法呢?
: 原文如下:
: You are given a set of n vertical line segments in the plane.
: Present an O(n) efficient algorithm to determine whether
: there exists a line that intersects all of these segments.
重发一篇...
假设这些垂直线段已经由左到右排列好
线段有上端点和下端点
所有线段上端点,找往朝下凸包 O(N) (monotone chain)
所有线段下端点,找到朝上凸包 O(N)
朝下凸包和朝上凸包之间的区域,就是直线可能存在的区域
如果两个凸包有内公切线,就存在一条直线穿过所有线段
如果两个凸包不相交(交集的面积是零),就有内公切线,就存在一条直线穿过所有线段
要判断两个凸包是否相交是O(N)