eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Шорт-трек

Шорт-трек

\includegraphics{https://static.e-olymp.com/content/bf/bf1855496929714f46c8b916e5ff9469cd8af837.jpg} Змагання по шорт-треку -- швидкісному бігу на ковзанах -- проводяться на невеликому льодовому овалі, порівняному з хокейноим майданчиком. Доріжка для спортсменів з однієї сторони обмежується бортиками майданчика, а сіншої -- фішками. Фішки розставляються так, що утворюють опуклий багатокутник. Задача постановки фішок не така проста, як може здатись на перший погляд. Організатори мають набір з N позицій-кандидатів, куда можна поставити фішку. За вимогами правил вони повинні поставити \textbf{K} фішок у деякі з позицій. Звичайно, набір з встановлених фішок повинен утворювати опуклий багатокутник. При цьому організатори хочуть по максимуму використати площу катка і встановити фішки так, щоб вони утворювали багатокутник максимально можливої площі. Більше того, існує прикмета, що, якщо всі інші позиції-кандидати виявляться поза багатокутником, змагання пройдуть вдало. Організатори дуже хочуть, щоб все було добре, тому необхідно обов'язково виконати умову прикмети. Необхідно допомогти організаторам встановити фішки на майданчику. \InputFile У першому рядку записані числа \textbf{N} і \textbf{K} (\textbf{3} ≤ \textbf{N} ≤ \textbf{20}, \textbf{3} ≤ \textbf{K} ≤ \textbf{10}, \textbf{K} ≤ \textbf{N}). Далі записано \textbf{N} рядків по два цілих числа -- координати позицій-кандидатів. Координати не перевищують \textbf{10000} за своїм абсолютним значенням. Ніякі три точки не лежать на одній прямій. \OutputFile У перший рядок необхідно вивести площу знайденого \textbf{K}-кутника з точністю строго один знак (навіть якщо він дорівнює нулю) після десяткової крапки. У другому рядку через пропуск вивести номери точок, з яких складено \textbf{К}-кутник, впорядкованв за зростанням. Точки пронумеровані у відповідності з їх появою у вхідних даних, нумерація починається з одиниці. Якщо можливо більше одного вірного розв'язку, виведыть той з них, у якому номер першої точки менший. Якщо номера першої точки співпадають, виведіть той з них, у якому номер другої точки найменший і так далі. Якщо розв'язку не існує, виведіть \textbf{-1}.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
5 4
0 0
-1 1
-1 -1
1 2
1 -2
Вихідні дані #1
2.5
1 2 3 4
Автор Бірюков С.В.
Джерело IV Відкрита олімпіада ЮФУ