Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$?
WLOG, let's rotate your problem so your segments are vertical. Let's say segment $i$ has $x$-coordinate $x_i$ and its low endpoint is $l_i$ and high endpoint $h_i$ (with $l_i &lt; h_i$).

Then our line through it (assuming it exists) has formula $y = ax + b$. Plugging in $x_i$ gives us $y_i = ax_i + b$. And thus we have $l_i \leq ax_i + b \leq h_i$.

Convince yourself that a solution line can always intersect at least one of two points: the one with the highest $l_i$ or the one with lowest $h_i$ (the most extreme requirements).

We try to find a solution line by plugging in one of the two extreme points $p$ (trying the other if the first doesn't work) to find $b = y_p - ax_p$. Then we can substitute to change the inequalities to:

$$l_i \leq a(x_i - x_p) + y_p \leq h_i$$

Now our only variable is $a$ so we can run through the $n$ inequalities, consistently choosing the strictest bounds for $a$ until we find the range of $a$ that works or that there's no solution.

Total runtime is $O(n)$ since we only have to try the above process twice and finding the extreme points also takes only $O(n)$ time.