Suppose we have $n$ lines $L_1, L_2, \dots, L_n$, where $L_i$ has the equation $y = a_i x + b_i$. We call $L_i$ the highest line at $x_0$ if for each $j \in \{1, 2, \dots, n\}$$$a_i x_0 + b_i \ge a_j x_0 + b_j.$$Goal: Find an algorithm in $O(n \log n)$ time to return a set of lines that are the highest lines in at least one point.Hint: Use the divide and conquer technique.Since we should use divide and conquer technique, I think I should split the problem into two subproblems with size of $n/2$ and try to solve these two first. I don't know what to do next. Thanks in advance.
An algorithm to find highest lines in at least one point
algorithms;computational geometry;divide and conquer