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

How to solve problem "E-Lite" from 0x11 Ural Championship (2013)
Автор Im_too_old_for_this_shit, 10 лет назад, По-английски

How to solve this task from Ural ? According to this it is somewhat standard. Thanks !

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

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Main ideas:

  1. Try to solve the problem if you know the directions of the answers in advance.
  2. Try to rotate in your mind a direction vector V = (cosθ, sinθ) continuously for all and to maintain the sorted order of the vectors given to you in the input data by their projection to vector V. Find how many times this sorted order changes. Find a polynomial (but slow) solution for the problem.
  3. Optimize the solution to obtain a feasible running time.

GL & HF :).

→ Ответить