※ 引述《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
你的算法怎么办?