Linear Convex Hull Trick

Revision en1, by dx24816, 2019-08-09 21:02:57

Hello,

Does anyone have a convex hull trick with linear complexity given that the lines you insert are in sorted slope order and the queries are also sorted? I used to just use the Li Chao tree, but it's not fast enough to solve APIO 2014 Split the sequence.

-dx24816

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dx24816 2019-08-09 21:02:57 299 Initial revision (published)