| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 10 | 1 | 1 | 33.333% |
К Жене на празднование дня рождения пришло $N$ человек, включая саму Женю, которой подарили огромный вкусный торт в форме выпуклого многоугольника. Она решила разделить его честно между всеми гостями и, конечно, собой. Честно --- это значит, что каждому человеку достанется ровно один кусок, причем всем достанутся куски одинаковой площади. При этом каждый кусок должен иметь связную форму простого многоугольника без самопересечений и самокасаний --- ведь подавать два раздельных куска одному человеку некрасиво. Торт, к сожалению, скоро испортится, поэтому его необходимо весь сразу съесть.
Женя попросила у вас помощи в нарезке торта. Напишите программу, которая разделит торт на $N$ кусков равной площади.
Первая строка входного файла содержит два целых числа $N$ и $M$ (1ドル \le N \le 15,ドル 3ドル \le M \le 100$) --- соответственно, количество людей на дне рождения и количество вершин в выпуклом многоугольнике, форму которого имеет торт.
Следующие $M$ строк содержат по паре целых чисел $x_i, y_i,ドル не превышающих по модулю 1000ドル$ --- координаты $i$-ой вершины выпуклого многоугольника в порядке обхода против часовой стрелки. Никакие три последовательные вершины не лежат на одной прямой.
В выходной файл выведите выведите $N$ описаний кусков, на которые надо разделить торт в следующем формате.
Сначала $k_i$ --- число вершин простого многоугольника, форму которого имеет $i$-ый кусок. При этом необходимо, чтобы $k_i$ не превышало 1000ドル$. После этого следуют $k_i$ пар чисел --- кординаты вершин многоугольника в порядка любого обхода. Выводите координаты с максимальной точностью.
2 3 0 0 2 2 -2 2
3 0 0 2 2 0 2 3 0 0 -2 2 0 2
3 4 -2 -2 2 -2 2 2 -2 2
4 -2 -2 -0.666667 -2 -0.666667 2 -2 2 3 -0.666667 -2 2 -2 -0.666667 2 3 2 -2 -0.666667 2 2 2
Так выглядит разрезание торта в первом примере:
А так во втором примере: