Час

09:54:44
25 May 2012
Версія для друку

Охорона ялинок

prb38

У лісі, лісі темному,
Де ходить хитрий лис,
Росла собі ялинонька,
І зайчик з нею ріс…

   Напередодні Нового Року зайці вирішили посилити охорону посадки ялинок. Для цього створили декілька ліній охорони. Спочатку вони ділянку лісу обтягнули дротом по периметру (опуклому многокутнику), відповідати за яку поставили самого сильного зайця. В середині цієї лінії охорони створили ще одну огорожу, біля якої поставили слабшого зайця і так далі. Відтак кожна ялинка була під охороною. Старший заєць, складаючи графік чергування зайців у лісі, звернувся до Вас за допомогою - підрахувати, яка найменша кількість охоронців потрібна для однієї зміни чергування по охороні ялинок.


Технічні умови

   Вхідні дані

   У першому рядку задано число N - кількість дерев. У наступному рядку через пропуск іде 2N чисел - координати дерев лісу.

   1N100, -1000Xi, Yi1000.

   Вихідні дані

   Єдине число - кількість зайців для охорони ялинок.


Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 5
Складність: 45% 28/51
Класифікація: Геометрія

Приклад

Приклад вхідних даних

7
1 1 5 7 3 2 4 2 4 3 6 3 3 4

Приклад вихідних даних

2


← Пошта спонсора Список задач Гроші спонсора →