Внимание!
Слова Ввод>
и Вывод< не вводятся и не
выводятся, мы их используем для пояснения
структуры примера!
Задача MINE
Миротворцы ООН в одной из горячих
точек планеты обезвреживали минное поле
следующим образом. Имея карту, на которой
каждая мина задана своими целочисленными
декартовыми координатами, они, обратив
внимание на то, что никакие 3 мины не лежат
на одной прямой, протянули специальный шнур
от мины к мине так, чтобы он образовал
выпуклый многоугольник минимального
периметра, при этом все остальные мины
оказались внутри многоугольника.
Обезвредив соединенные мины, они вновь
протянули шнур по тому же принципу и опять
обезвредили соединенные шнуром мины. Так
продолжалось до тех пор, пока очередной
шнур оказалось невозможно протянуть,
руководствуясь изложенными правилами.
Сколько мин осталось обезвредить и сколько
раз саперам приходилось протягивать шнур?
Ввод-вывод
Вы вводите с клавиатуры количество мин N (3
<= N <= 1000), далее - N раз считываете с
клавиатуры по 2 целых числа X и Y
через пробел - координаты очередной мины (-32000
<= X <= 32000), (-32000 <= Y <= 32000).
Вы выводите на экран два числа через пробел
- количество оставшихся мин и количество
операций по натягиванию шнура.
Пример
Ввод> 9
Ввод>0 0 0 8 6 8 6 0 1 1 1 7 5 7 5 1 3 2
Вывод< 1 2 |