Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя 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

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

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

click

→ Ответить
  • »
    »
    4 часа назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    OMG BRO, thank you very much!

    → Ответить
»
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

→ Ответить