→ esrever:divide & conquer ? 12/04 00:14
→ seanwu:二維線性規劃是expected O(n)嗎? 12/04 23:01
→ seanwu:啊啊沒事，找到worst case O(n)的做法了 12/04 23:24
推 DJWS:想請叫一下樓上 worst case O(n) 的做法是什麼？ 12/05 08:22
→ DJWS: 教 12/05 08:22
推 DJWS:多謝! 12/06 15:32
我在網路上看到一個問題：
給定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.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.170.195.148