Максимальный выпуклый многоугольник
Автор задачи: Метельский И.С.
Первоисточник: Неофициальный сайт белорусских олимпиад. Задачи со сборов к IOI (2002-2003). Многоугольник
URL первоисточника: http://byoi.narod.ru/
Задачу добавил: elena
Успешно сдано решений: 0
Время на тест - 4 с.
На плоскости задано N различных точек. Никакие три из них не лежат на одной прямой. Необходимо выбрать максимальное количество точек M таким образом, чтобы выбранные точки образовывали выпуклый многоугольник.
Формат входного файла input.txt:
Первая строка содержит целое число N (3<=N<=300).
Следующие N строк содержат координаты точек. Каждая строка описывает ровно одну точку и состоит из двух вещественных чисел X и Y (-1000 <= X, Y <= 1000), разделенных пробелом. X - абсцисса очередной точки, а Y - ее ордината. Числа X и Y содержат не более 3 знаков после запятой.
Формат выходного файла output.txt:
Первая строка - одно целое число - M.
Пример входного файла
7
0 2
2 0
2 3
5 0
5 3
6 6
6 -7
Пример выходного файла
5