USACO 2020 January Platinum 3: Falling Portals

Problems and Contests
#1

The editorial mentions that we should binary search for the intersection of the line with the convex hull. I am wondering why binary search is used here instead of ternary search.

Screen Shot 2020-11-25 at 7.35.39 PM
Screen Shot 2020-11-25 at 7.35.39 PM1030Ă—924 54.6 KB

In the diagram above, the points in the hull begin and end as non-optimal, and the best intersection (line with the least non-negative slope) will lie somewhere in the middle. So, we should be able to ternary search for that intersection.

I guess I can see how binary search might be used (binary searching on slopes and checking for intersection with the hull) but wouldn’t ternary search on the hull make our lives much easier?

I might be missing something obvious, so any help would be greatly appreciated!

#2

I think the hull in your diagram should be concave up rather than concave down.

1 Like
#3

I managed to get AC by maintaining 2 hulls (one “top left” concave down hull when processing from bottom-up and one “bottom right” concave up hull from top-down), and then ternary searching for the point with least non-negative slope.

I think this method is slightly different from the one described in the editorial, which is why the confusion originated.

Thanks for the help anyway!