Входные данные: input.txt Выходные данные: output.txt Время на тест: 1 секунда Тесты к задаче:Скачать Автор задачи: Лапо А.И.
На координатной плоскости своими координатами заданы N различных точек. Требуется найти максимальное количество k выпуклых многоугольников, для которых выполняются следующие условия:
1. вершинами многоугольников могут являться только заданные точки;
2. каждая из заданных точек должна использоваться в качестве вершины только одного многоугольника (многоугольниками будем также считать отрезок и точку);
3. любые два построенных многоугольника пересекаются, их пересечением всегда является один из этих двух многоугольников.
Требуется вывести k - количество найденных многоугольников и s -количество вершин многоугольника наибольшей площади.
Ввод данных из файла INPUT.TXT
В первой строке - целое число N (1<N<145). В каждой из следующих N строк - пара координат xi yi (вещественные числа через пробел).
Вывод данных в файл OUTPUT.TXT:
целые числа k и s через пробел.
Пример ввода
9
0 0
1 1
2 0
2 0.5
2 2
3 1
4 0
2.5 0.5
0 2
Пример вывода
3 4
Действительно, искомыми многоугольниками являются трапеция, треугольник и отрезок, изображенные на рисунке.