Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Максимальный выпуклый многоугольник

Автор задачи: Метельский И.С.

Первоисточник: Неофициальный сайт белорусских олимпиад. Задачи со сборов к 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

Сдать задачу

Задать вопрос жюри по этой задаче