Гондор — страна холмов. В незапамятные времена владыки Гондора решили построить
на некоторых холмах сторожевые башни для охраны королевства. После подсчёта имеющихся в казне средств
выяснилось, что их хватает только на постройку пяти башен. Король Гондора развернул карту королевства с отмеченными
на ней 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)