Please help me in this past ICPC problem

Solutions: https://swerc.eu/theme/slides/problemanalysis.pdf

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.

1 Like

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.

1 Like