※ 引述《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