| Автор: | А. Жуплев, А. Кленин | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt |
Во время военных учений командиру разведывательного отряда было поручено провести рекогносцировку расположения условного противника с помощью новейшего беспилотного летательного аппарата.
С энтузиазмом взявшись за выполнение боевой задачи, отважные разведчики произвели успешный запуск аппарата и получили фотографию вражеских позиций. Для дополнительной скрытности запуск был произведён в тёмное время суток, то есть ночью.
К сожалению, оказалось, что фотокамера аппарата обладает низкой светочувствительностью. Поэтому на снимках видны только костры часовых, расположенные по периметру позиций условного противника.
Командиру очень хочется отчитаться об успешном выполнении задания, поэтому ему необходимо нарисовать какой-нибудь план расположения вражеских частей, соответствующий полученной фотографии. Согласно уставу, расположение каждой части является выпуклым многоугольником, в углах которого разожжены костры. Командир надеется, что в штабе не заметят, если он пропустит в своём плане не более пяти костров, присутствующих на фотографии.
Требуется написать программу, которая по различным N точкам на плоскости построит непустой набор из выпуклых многоугольников, которые:
Входной файл содержит число точек N, за которым следует N пар целых чисел xi yi — координаты точек.
Выходной файл должен содержать число многоугольников M, за которым следуют M описаний многоугольников. Каждое описание состоит из числа вершин K, за которым следует K чисел — номера точек, являющихся вершинами многоугольника, перечисленными в порядке обхода. Нумерация вершин начинается с 1.
Если существует более одного решения, выведите любое из них.
3 ≤ N ≤ 1000, − 105 ≤ xi, yi ≤ 105
Никакие три точки не лежат на одной прямой.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|