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?
I am sorry that you had to wait, I am running sick lately and am at bedrest. Hope I wasnt too late dear.
You can use the rotating calipers technique to solve this problem.
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.