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

Автор:А. Жуплев, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Во время военных учений командиру разведывательного отряда было поручено провести рекогносцировку расположения условного противника с помощью новейшего беспилотного летательного аппарата.

С энтузиазмом взявшись за выполнение боевой задачи, отважные разведчики произвели успешный запуск аппарата и получили фотографию вражеских позиций. Для дополнительной скрытности запуск был произведён в тёмное время суток, то есть ночью.

К сожалению, оказалось, что фотокамера аппарата обладает низкой светочувствительностью. Поэтому на снимках видны только костры часовых, расположенные по периметру позиций условного противника.

Командиру очень хочется отчитаться об успешном выполнении задания, поэтому ему необходимо нарисовать какой-нибудь план расположения вражеских частей, соответствующий полученной фотографии. Согласно уставу, расположение каждой части является выпуклым многоугольником, в углах которого разожжены костры. Командир надеется, что в штабе не заметят, если он пропустит в своём плане не более пяти костров, присутствующих на фотографии.

Требуется написать программу, которая по различным N точкам на плоскости построит непустой набор из выпуклых многоугольников, которые:

  1. являются невырожденными и имеют не менее трёх вершин;
  2. не имеют общих точек между собой;
  3. имеют вершины только в данных точках;
  4. используют в качестве вершин все имеющиеся точки, за исключением не более пяти штук.

Формат входного файла

Входной файл содержит число точек N, за которым следует N пар целых чисел xi yi — координаты точек.

Формат выходного файла

Выходной файл должен содержать число многоугольников M, за которым следуют M описаний многоугольников. Каждое описание состоит из числа вершин K, за которым следует K чисел — номера точек, являющихся вершинами многоугольника, перечисленными в порядке обхода. Нумерация вершин начинается с 1.

Если существует более одного решения, выведите любое из них.

Ограничения

3 ≤ N ≤ 1000,  − 105 ≤ xi, yi ≤ 105

Никакие три точки не лежат на одной прямой.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
-1 -1
1 1
1 -1
-1 1
3 7
0
2
9
-2 4  3 -2  3 2  -2 -4  2 5  -7 -3  7 2  1 -3  -4 -1
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
2
4  5 1 3 7
4  9 2 8 6

0.116s 0.016s 15