dx24816's blog

Linear Convex Hull Trick
By dx24816, history, 5 years ago, In English

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

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote about it once: link

→ Reply