I have a problem in Problem-K. The solution states that we find the distance of the point furthest away from each side of the convex hull individually. But I can’t see how to do that in O(n) time. It is trivial to do it in O(n^2) but I don’t know to find it in amortized O(n) time. Can someone help me?
You can use the rotating calipers technique to solve this problem.
I am sorry that you had to wait, I am running sick lately and am at bedrest. Hope I wasnt too late dear.
Oh, it was no problem at all. Thank you and get well soon.
Hmm…this looks interesting. Thanks! I’d upvote you if I had enough rep.