Can anyone help me with CF Problem F. Escape through Leaf (Convex Hull Trick)

help
,
1

Guys

I’m trying to solve this problem and getting RE in this cpp submission while having trouble implementing efficient fully dynamic variant as mentioned here.

Can anyone help me preferably in implementing Fully Dynamic variant of Convex Hull trick or correcting me in cpp solution with my mistake?

Thanks a lot.

2 Likes
2

Lichao Segment Tree
This may interest you. It is easier to implement than a dynamic cht and has no disadvantages that I know of. I learnt it recently so I could be wrong about that.

1 Like
3

Here’s my submission using LiChao Tree for Problem POLY 2nd subtask. https://www.codechef.com/viewsolution/18006110

It gave me very poor runtime as compared to simple CHT implementation. Any ideas why??

4

What sorcery is this: 35514964?

1 Like
5

Something beyond the world it seems to me. 78ms runtime :o

Can’t understand idea at all.

6

First of all the implementation you are following has many bugs in the add_line() function. Here is a fixed version: pastebin link.

And secondly, your swapping method below

if(tmp.size() > h.size()){
    hull_optimizer t = tmp;
    tmp = h;
    h = t;
}

is not good because writing x = y for 2 objects in C++ makes x an exact copy of y. So here you will be copying the hull with all its lines back and forth. The complexity no longer remains \mathcal{O}(n \log n).
To maintain the small-to-large trick and \mathcal{O}(n \log n) complexity you want to swap pointers instead of copying whole objects. If you don’t want to deal with pointers you could also swap array indices like so: 36878762.

1 Like
7

I guess it’s time for me to learn cpp.

Thanks a lot. :slight_smile: