Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1432. Учебная разведка
Жадные алгоритмыБыстрая сортировка
Олимпиадные задачи на русском языке
| 24/06/2010 | Лето 2010 дорешивание ( 6D) |
| 05/07/2010 | Лето 2010 - 6 (D) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Во время военных учений командиру разведывательного отряда было поручено провести рекогносцировку расположения условного противника с помощью новейшего беспилотного летательного аппарата.
С энтузиазмом взявшись за выполнение боевой задачи, отважные разведчики произвели успешный запуск аппарата и получили фотографию вражеских позиций. Для дополнительной скрытности запуск был произведён в тёмное время суток, то есть ночью.
К сожалению, оказалось, что фотокамера аппарата обладает низкой светочувствительностью. Поэтому на снимках видны только костры часовых, расположенные по периметру позиций условного противника.
Командиру очень хочется отчитаться об успешном выполнении задания, поэтому ему необходимо
нарисовать какой-нибудь план расположения вражеских частей, соответствующий полученной фотографии.
Согласно уставу, расположение каждой части является выпуклым многоугольником, в углах которого разожжены костры.
Командир надеется, что в штабе не заметят, если он пропустит в своём плане не более пяти костров, присутствующих на фотографии.
Требуется написать программу, которая по различным `N` точкам на плоскости построит
непустой набор из выпуклых многоугольников, которые:
- являются невырожденными и имеют не менее трёх вершин;
- не имеют общих точек между собой;
- имеют вершины только в данных точках;
- используют в качестве вершин все имеющиеся точки, за исключением не более пяти штук.
Формат входного файла
Входной файл содержит число точек `N`, за которым следует `N` пар целых чисел `x_i\ y_i` – координаты точек.
Формат выходного файла
Выходной файл должен содержать число многоугольников `M`, за которым следуют `M` описаний многоугольников.
Каждое описание состоит из числа вершин `K`, за которым следует `K` чисел – номера точек, являющихся вершинами многоугольника, перечисленными в порядке обхода. Нумерация вершин начинается с 1.
Если существует более одного решения, выведите любое из них.
Ограничения
`3\ ≤\ N\ ≤\ 1000`, `-10^5\ ≤\ x_i,\ y_i\ ≤\ 10^5`
Никакие три точки не лежат на одной прямой.
Пример ввода 1
5 -1 -1 1 1 1 -1 -1 1 3 7
Пример вывода 1
0
Пример ввода 2
9 -2 4 3 -2 3 2 -2 -4 2 5 -7 -3 7 2 1 -3 -4 -1
Пример вывода 2
1 7 3 2 8 4 9 1 5
Пример ввода 3
9 -2 4 3 -2 3 2 -2 -4 2 5 -7 -3 7 2 4 -6 -4 -1
Пример вывода 3
2 4 5 1 3 7 4 9 2 8 6
