※ 引述《DJWS (...)》之銘言：
: ※ 引述《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)
嗯, 抱歉我看不懂你想說折麼.
你的朝上凹包 是 convex polygen 嗎?
朝下凹包是甚麼? concave polygen ?
要是只有三條線, 你永遠會找到 convext polygen
你的演算法怎麼辦?