Шорт-трек#738

Шорт-трек

1 секунда
64 мегабайти
Складна

Змагання з шорт-треку проводяться на невеликому льодовому овалі, схожому на хокейний майданчик. Траса спортсменів з одного боку обмежена бортом, а з іншого — маркерами. Ці маркери розташовують так, щоб вони утворювали опуклий багатокутник.

Встановити ці маркери не так просто, як здається на перший погляд. Організатори мають набір із кандидатних позицій для встановлення маркерів. За правилами треба встановити рівно маркерів у деяких із цих позицій. Встановлений набір маркерів має утворювати опуклий багатокутник. Організатори також прагнуть максимально використати площу льодової арени, розташувавши маркери так, щоб площа багатокутника була найбільшою можливою. Крім того, існує повір'я, що якщо всі інші кандидатні позиції лежать поза межами багатокутника, змагання пройдуть успішно. Організатори щиро бажають виконати цю умову. Вам потрібно допомогти організаторам розставити маркери на льодовій арені.

Вхідні дані

У першому рядку задано числа та (3 \le N \le 20, 3 \le K \le 10, K \le N). Далі у кожному з наступних рядків задано по два цілих числа — координати однієї кандидатної позиції. Координати за модулем не перевищують . Жодні три точки не лежать на одній прямій.

Вихідні дані

У першому рядку потрібно вивести площу вибраного -кутника, округлену до рівно однієї десяткової після коми (навіть якщо це нуль). У другому рядку виведіть у зростаючому порядку номери точок, що утворюють цей -кутник, розділені пробілами. Точки нумеруються за порядком, у якому вони дані у вхідних даних, починаючи з .

Якщо існує декілька допустимих рішень, виведіть те, у якого найменший номер першої точки. Якщо ці номери збігаються — те, у якого найменший номер другої точки і т.д.

Якщо рішення не існує, виведіть -1.

Приклади

Приклад 1

Loading
Loading