|
|
back to boardA hint for confused solvers. 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. |
|
|