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

1578. Охота на мамонта

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Последний мамонт убегает от стаи доисторических охотников. Охотники свирепы, голодны и вооружены дубинами и каменными топорами. Чтобы быстрее скрыться от преследователей, мамонт пытается запутать свои следы. Его траектория имеет форму ломаной (не обязательно простой). Более того, все пары соседних звеньев ломаной образуют острые углы (угол в 0 градусов также будем считать острым).
После того, как мамонт скрылся из виду, обнаружилось, что, убегая, он выполнил ровно N поворотов. Известны точки, в которых мамонт совершал повороты, а также точка, где началась погоня, и точка, где мамонт скрылся из виду (всего N + 2 точки). Требуется восстановить возможную траекторию движения мамонта.

Исходные данные

В первой строке дано целое положительное число N, не превосходящее 2000. Далее в N + 2 строках перечислены координаты вершин ломаной — траектории мамонта. Все координаты — целые числа в пределах от −2000 до 2000. Любые 2 вершины ломаной имеют различные координаты.

Результат

Если никакая ломаная с вершинами в данных точках не может являться траекторией мамонта, выведите NO. Иначе в первой строке выведите YES, а во второй — траекторию мамонта в виде последовательности номеров точек (точки нумеруются от 1 до N + 2 в том порядке, в котором они перечислены во входных данных). Если задача имеет несколько решений, выведите любое.

Примеры

исходные данныерезультат
2
0 0
1 1
1 2
2 0
YES
1 3 4 2
2
0 0
0 1
0 2
0 3
YES
1 3 2 4
Автор задачи: Александр Ипатов
Источник задачи: XIV Открытое командное первенство школьников Свердловской области по программированию