We can do this by divide and conquer, firstly sort the n lines in increasing order of slopes, then recursively find the upper envelop of first n/2 and last n/2 lines.

The combine step will require us to merge these upper envelops. They will only intersect at a unique point say x (why?), now all we have to do is find x. We can do it using two pointers, initialise them to the start of both upper envelop, now find the point of intersection of these lines say z, let u,v be their point of discontinuity in the envelop, if z<u and z<v return z else if z<u and z>v increment right pointer, else if z<v z>u increment left pointer else increment both pointers.

since the combine step takes O(n)

Time compleixty will be O(nlogn)