※ 引述《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 你的演算法怎麽办? -------- well, my intuition is.. Let's define the vertical line as (u, v) u as the upper point, v as the lower point. Assuem the lines are sorted from left to right. Then, we only need to compare two lines: u_1 - highest v_i and u_1 - lowest u_i , i \= 1 -- 赵客缦胡缨，吾钩霜雪明。银鞍照白马，飒沓如流星。 十步杀一人，千里不留行。是了拂衣去，深藏身与名。 闲过信陵饮，脱剑膝前横。将炙啖朱亥，持觞劝侯赢。 三杯吐然诺，五岳倒为轻。眼花耳热後，意气素霓生。 就赵挥金锤，邯郸先震惊。千秋二壮士，烜赫大梁城。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 96.41.13.29