ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1418. Армейская история

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Военные захотели усилить охрану космодрома. Было решено, что он должен быть огорожен как можно большим числом заборов, а вдоль каждого из них вокруг космодрома должна ходить вооруженная охрана. Издали приказ, и начали готовить проект.
Желая выслужиться, прапорщик Дуров направил роту солдат вкапывать столбы для забора, не дожидаясь проекта. Солдаты, не долго думая, наставили столбов куда попало. Помогите прапорщику решить, как на этих столбах сделать побольше заборов из колючей проволоки.

Исходные данные

В первой строке содержится целое число 3 ≤ N ≤ 4000 — количество вкопаных столбов. В каждой из последующих N строк содержатся два целых числа 0 ≤ x, y ≤ 10000 — координаты столба. Естественно, все столбы вкопаны в разных точках.

Результат

Выведите максимально возможное количество заборов, которые можно построить. Заборы должны являться многоугольниками без самопересечений, с углами в точках столбов. Заборы не должны касаться или пересекаться, и должны быть вложенными один в другой, чтобы вдоль каждого забора патруль мог обойти космодром и снаружи, и изнутри.

Пример

исходные данныерезультат
4
100 100
200 100
100 200
300 300
1
Автор задачи: Алексей Лахтин
Источник задачи: Чемпионат Уральского государственного университета, 29 октября 2005