printРабочее место участника

printЗадачи

1432. Учебная разведка

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
Источник: Весенний турнир ДВГУ, 2010
loading