Задача №1392. Великий Флатландский Забор
С незапамятных времен граница страны Флатландия имеет форму N-угольника без самопересечений и самокасаний (необязательно выпуклого). В каждой из вершин этого многоугольника король построил по башне.
В целях увеличения обороноспособности государства на его территории король задумал построить Великий Флатландский Забор. По причине многолетней войны ресурсов хватает на строительство ровно K стен (неважно, какой длины). Каждая стена должна соединять ровно две башни по прямой и не должна даже частично выходить за пределы Флатландии. К тому же, Забор должен представлять собой не более чем K-угольник также без самопересечений и самокасаний (углов может оказаться и меньше, чем K, так как некоторые соседние стены могут лежать на одной прямой). Военный советник настаивает на том, что площадь защищенной области должна быть как можно больше.
Ваша задача — помочь спроектировать такой Забор.
В первой строке записаны два целых числа N и K (3 ≤ K ≤ N ≤ 230). В следующих N строках содержатся пары целых чисел — координаты башен в порядке обхода границы против часовой стрелки. Гарантируется, что никакие три последовательные башни не лежат на одной прямой. Все координаты не превосходят 1000 по абсолютной величине.
В первую строку запишите максимальную площадь, которую можно защитить Забором, с точностью до пяти знаков после десятичной точки. Во второй строке должно быть Q — количество выбранных башен.
Будем считать, что башни занумерованы числами от 1 до N в порядке перечисления их во входном файле. Во третью строку через пробел выведите номера Q башен, которые будут вершинами Забора, в порядке его обхода против часовой стрелки.
Частичные ограничения
Первая группа состоит из тестов, в которых N ≤ 20 и граница Флатландии представляет собой выпуклый многоугольник.
Вторая группа состоит из тестов, в которых N ≤ 20, но граница может быть уже любой.
3 3 0 0 1 0 0 1
0.50000 3 1 2 3
6 5 0 0 7 0 4 3 4 4 3 4 0 7
24.50000 5 1 2 3 5 6
4 3 0 0 1 3 0 2 -2 -2
2.00000 3 1 3 4