Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Формула 001

(Время: 2 сек. Память: 32 Мб Сложность: 57%)

Мальчик Миша собирается участвовать в школьных соревнованиях по гонкам с препятствиями по версии «Формула 001». Но к любым соревнованиям необходимо готовиться. Младший брат Миши, Ральф, не так силен в гонках с препятствиями, как его старший брат, но зато он обладает незаурядной фантазией. Он решил помочь брату и придумал игру, играя в которую, можно существенно увеличить свой опыт в вождении гоночного автомобиля.

Игра состоит в следующем. Пусть у нас есть бесконечное игровое поле, покрытое бесконечной квадратной сеткой. Некоторое множество узлов этой сетки отмечено. Назовем это множество S. В игре участвуют несколько игроков. У каждого игрока есть машина – фигура, которая может находиться только в узлах из множества S. В начале игры все машины находятся в различных начальных узлах. Ход каждого игрока состоит в перемещении машины в некоторый узел из множества S, возможно, тот же самый. Цель игры – добраться до определенного, финишного узла первым.

Ход происходит по следующим правилам. Пусть на предыдущем шаге машина была перемещена на вектор (X, Y) (если это первый шаг, то X=0 и Y=0). Тогда за один текущий ход машину можно передвинуть на один из следующих векторов: (X−1, Y−1), (X−1, Y), (X−1, Y+1), (X, Y−1), (X, Y), (X, Y+1), (X+1, Y−1), (X+1, Y) и (X+1, Y+1).

Конечно, на какой-либо из этих векторов машину переместить можно только при том условии, что после этого она попадет в узел из множества S. Если ход сделать нельзя, то игрок считается проигравшим и выбывает из игры.

Некоторое время поиграв в эту игру, Миша и Ральф занялись ее анализом. В данный момент они хотят узнать, за какое наименьшее число ходов из стартового узла возможно попасть в финишный. Сами они эту задачу решить не смогли и обратились за помощью к Вам. Помогите им!

Входные данные

В первой строке входного файла INPUT.TXT находится N – число элементов множества S. 2 ≤ N ≤ 1000. В последующих N строках находятся координаты узлов из этого множества – целые числа Xi, Yi (−109 ≤ Xi, Yi ≤ 109).

Никакие два узла во входном файле не совпадают. Занумеруем эти узлы, начиная с 1, в порядке их описания во входном файле. Стартовым узлом будет являться узел с номером 1, финишным узел с номером N .

Выходные данные

В выходной файл OUTPUT.TXT выведите -1, если добраться до финишного узла невозможно. Иначе, в первой строке выведите минимальное требуемое число ходов K . Во второй выведите K+1 число – номера посещенных узлов в порядке посещения. Первым узлом должен быть узел с номером 1, последним – узел с номером N .

Примеры

INPUT.TXTOUTPUT.TXT
13
0 0
0 1
0 2
2
1 2 3
23
0 0
0 2
0 3
-1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru