Страница: 1 [Всего задач: 1]      

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

Входные данные
В первой строке входного файла через пробел записаны два целых числа M и N (3 ≤ M ≤ N ≤ 10). Во второй строке перечислены N точек, каждая из которых задана парой своих координат. Координаты являются вещественными числами и разделяются пробелом.

Выходные данные
В первую строку выходного файла нужно вывести площадь искомого M-угольника, а во вторую – номера точек, являющихся вершинами этого M-угольника (в порядке обхода по или против часовой стрелки). Номера точек разделяются пробелом. Если вариантов решений несколько, то достаточно выдать любой из них. Если же ни один M-угольник с указанными свойствами построить невозможно, то выходной файл должен содержать единственное число 0.

Пример входного файла
3 4
0 0 0 1 1 0 1 1

Пример выходного файла
0.5
1 2 3

Прислать комментарий

Решение

Страница: 1 [Всего задач: 1]