Query regarding the O(1) convex hull trick

Правка en2, от heyyolol, 2020-05-05 21:21:31

Hi, as far as I know, the O(1) convex hull trick (using either vector or deque) requires the lines to be inserted in strictly increasing gradients.

However is there a condition that must be satisfied for x in the query part? I have always previously thought for a maximum finding convex hull, x must be queried in increasing order, however there was one question which i managed to AC by ignoring the fact that x in the query must be increasing. So was the TCs weak? or was what I had previously thought wrong lol?

Btw what i did in the question: sort the lines by increasing m, where i'll set m to be the gradient of the line which I'll insert, and do query(-2*m) (Maybe it's something to do with the negative? I'm not too sure)

Thanks in advance.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский heyyolol 2020-05-05 21:21:31 2 Tiny change: 'e negative i? I'm not ' -> 'e negative? I'm not '
en1 Английский heyyolol 2020-05-05 21:20:09 801 Initial revision (published)