С незапамятных времен граница страны Флатландия имеет форму 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
Есть прямоугольный стол для игры в бильярд размером \(N\)x\(M\). Стол расположен в системе координат так, что его углы находятся в точках с координатами (0,0), (\(N\),0), (\(N\),\(M\)), (\(M\),0).
На столе лежат черный и белый шары. Игрок ударяет по черному шару, задавая ударом направление его движения. Шар летит в заданном направлении, отскакивая от стенок стола по закону отражения. Когда черный шар ударяет по белому шару, то черный шар останавливается, а белый начинает двигаться в том направлении, куда летел в момент удара черный. После этого белому шару запрещается ударять черный шар.
Задача игрока — загнать белый шар в одну из луз, расположенных в углах стола. При этом до попадания в лузу черный и белый шары должны удариться о стенки стола суммарно как можно меньше раз, но не более \(K\) раз.
Сначала вводятся размеры стола \(N\) и \(M\) (3≤\(N\)≤1000, 3≤\(M\)≤1000). Далее записано число K (0≤K≤200). Затем записано две пары чисел \(X_1\), \(Y_1\), \(X_2\), \(Y_2\) – начальные координаты черного шара и начальные координаты белого шара (1≤\(X_1\)≤\(N\)–1, 1≤\(Y_1\)≤\(M\)–1, 1≤\(X_2\)≤\(N\)–1, 1≤\(Y_2\)≤\(M\)–1). Гарантируется, что начальные положения шаров не совпадают, и изначально шары находятся строго внутри стола.
Все числа целые.
Выведите минимальное суммарное количество ударов черного и белого шаров о стенки стола до попадания белого шара в лузу. Если попасть белым шаром в лузу, сделав не более K ударов, невозможно, выведите –1 (минус один).
4 4 3 2 1 2 3
1
4 4 200 1 1 1 3
-1
5 4 3 4 1 4 3
3
5 4 0 3 2 4 3
0