Время

14:51:30
24 May 2012
Версия для печати

Границы

prb229   Древнее государство НеРим имело границу в виде выпуклого многоугольника, определенного оградой. Государство НеРим постоянно увеличивало свою территорию, побеждая своих врагов и захватывая новые земли.

   Когда новая граница образовывала выпуклый многоугольник, неримляне разрушали старую ограду и строили новую.

   Cовременные историки решили заняться исследованием развития древнего НеРима. Однако единственное, что у них было, – это координаты отверстий от столбов, которые размещались ранее в вершинах многоугольников.

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


Технические условия

   Входные данные

   Входной файл состоит из нескольких тестов. Первая строка каждого теста показывает количество отверстий. В каждой из следующий строк – целые координаты X и Y одного отверстия, разделенные запятой. Значения координат не превышают 1000. Координаты отверстий записаны в случайном порядке. Входной файл не содержит пустых строк.

   Выходные данные

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


Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 50
Сложность: 36% 9/14

Пример

Пример входных данных

10
7, 16
12, 10
1, 22
23, 22
3, 6
14, 1
17, 20
27, 24
3, 20
11, 5

Пример выходных данных

3


← Охота на крокодила – 2 Список задач Парад скобок →