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