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

Автор SecondThread, история, 6 лет назад, По-английски

AlgorithmsThread 6: Convex Hulls

Hi everyone! I just released Episode 6 of AlgorithmsThread (now rebranded from Algorithms Dead after frodakcin's epic suggestion).

In it, I talk about:

  • Getting the convex hull
  • Checking if a point is in a convex hull in $$$O(log(n))$$$
  • Finding the farthest point in some direction in $$$O(log(n))$$$
  • The problem Trash Removal with $$$O(n^3)$$$ -> $$$O(n^2)$$$ -> $$$O(n*log(n))$$$ solutions
  • The more difficult problem Troop Mobilization from ICPC South East Regionals

I hope you enjoy. Feel free to ask questions below, as usual :)

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Extremely helpful, please keep going! You're simply great.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Can someone recommend cf problems that use these techniques?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

One of my favourite problems on convex hull trick : Link