Please help me in this past ICPC problem

help
,
1

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?

2

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
3

You can use the rotating calipers technique to solve this problem.

4

Oh, it was no problem at all. Thank you and get well soon.

5

Hmm…this looks interesting. Thanks! I’d upvote you if I had enough rep.

1 Like