images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:33:35

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2292. Хеллоуин

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Эрик обходит на Хеллоуин дома соседей, что собрать сладости. Он может посещать дома соседей по несколько раз и соседи каждый раз дают угощения, но Эрик не может посещать дом дважды подряд. Перед повторным визитом он должен посетить какой-нибудь другой дом. Кроме того, по мере заполнения мешка, Эрику становится тяжелее идти, поэтому пройденное расстояние при каждом переходе между домами соседей должно строго уменьшаться.
Эрик начинает путешествие от своего дома в точке `(0,0)`. Дома соседей находятся в точках с координатами `(X_i,\ Y_i)`. Координаты всех домов различны.
Вычислите, какое максимальное количество угощений сможет собрать Эрик, прежде чем расстояние до следующего дома ему покажется слишком большим (т.е. большим или равным предыдущего пройденного расстояния).
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 2000`) – количество домов соседей. Следующие `N` строк содержат по два целых числа `X_i` и `Y_i` (`-10000\ ≤\ X_i,\ Y_i\ ≤\ 10000`) – координаты домов.
Вывести одно целое число – максимальное количество угощений, которое сможет собрать Эрик.

Пример ввода

5
3 1
3 2
3 3
4 10
5 8

Пример вывода

6
Пояснение к примеру: Сначала Эрик идет из точки (0,0) в точку (4,10), преодолевая расстояние `sqrt(116)`, оттуда в точку (3,1) и проходит расстояние `sqrt(82)`, далее в точку (5,8), находящуюся на расстоянии `sqrt(53)`, а из нее в точку (3,3) на расстоянии `sqrt(29)`, затем снова в точку (3,1) на расстоянии 2 и, наконец, в точку (3,2) на расстоянии 1.
loading