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

Открытое личное первенство УрГУ 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Сторожевые башни

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Гондор — страна холмов. В незапамятные времена владыки Гондора решили построить на некоторых холмах сторожевые башни для охраны королевства. После подсчёта имеющихся в казне средств выяснилось, что их хватает только на постройку пяти башен. Король Гондора развернул карту королевства с отмеченными на ней N холмами. Чтобы стражи на башнях могли эффективно обозревать местность, башни должны были располагаться в вершинах некоторого выпуклого пятиугольника. Мудрый Гэндальф, состоящий в дружбе с королём, нашёл решение этой задачи. И вот стражи на башнях не смыкают глаз в течение уже тысячи лет…
Интересно, какие бы пять холмов для постройки башен выбрали вы на месте Гэндальфа?

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

В первой строке дано целое число N (5 ≤ N ≤ 5000). В следующих N строках приведены координаты холмов на карте Гондора (Xi, Yi). Координаты — целые числа, по модулю не превосходящие 108. Никакие три холма не лежат на одной прямой.

Результат

Выведите в первой строке «No», если не можете выбрать среди холмов нужные пять (возможно, Гэндальф ошибся). Иначе выведите в первой строке «Yes», а во второй строке через пробел пять различных чисел от 1 до N — номера выбранных вами холмов в порядке обхода выпуклого пятиугольника против часовой стрелки. Разделяйте номера пробелами.

Пример

исходные данныерезультат
6
1 0
0 1
1 2
2 0
2 2
3 1
Yes
2 1 4 5 3
Автор задачи: Александр Ипатов
Источник задачи: Восьмое открытое личное первенство УрГУ (3 марта 2007)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1538. Сторожевые башни