我在网络上看到一个问题:
给定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.