Im_too_old_for_this_shit's blog

How to solve problem "E-Lite" from 0x11 Ural Championship (2013)
By Im_too_old_for_this_shit, 10 years ago, In English

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

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

»
10 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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 :).

→ Reply