ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1130. Никифор на прогулке

A hint for confused solvers.
Послано 198808xc 13 авг 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.