Блог пользователя dx24816

Convex Hull Trick Implementation
Автор dx24816, история, 6 лет назад, По-английски

Hello,

I have recently been reading about the convex hull trick (https://wcipeg.com/wiki/Convex_hull_trick), but I can't seem to implement the fully dynamic version. Can anyone point me to a C++ implementation of the fully dynamic convex hull trick? Thanks!

-dx24816

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

click

→ Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

I use dynamic connectivity implementation and simple implementation of convex hull trick. You can see it here. It's O((n+q)logqlogn)

operations:

  • add

  • delete

  • query

→ Ответить