ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1130. Nikifor's Walk

A hint for confused solvers.
Posted by 198808xc 13 Aug 2008 11:43
Many people above have solved this problem, but they didn't express their thought well.

The key is this:
For ANY 3 vectors in the set with module not exceeed L,
we can ALWAYS choose 2 of them and, with choosing the direction, make the module of their sum not exceed L.
(this can be proved by geometry)

So, we choose the two and reduce them to one (simply adding them and record the direction).
Thus, we can reduce the amount of vectors by this until there are only TWO.
At last, for any two vectors which has the module not longer than L,
we can make the module of their sum not exceed L*sqrt(2).

And that's all the key.
What's left is to find a way to programme.
Use tree to store the father-son relation is a good choice.

Maybe it will help you, maybe not for my poor English.