|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
09.10.2011, 12:40 | #1 |
Пользователь
Регистрация: 16.09.2011
Сообщений: 43
|
задача
Миротворцы ООН в одной из горячих точек планеты обезвреживали минное поле следующим образом. Имея карту, на которой каждая мина задана своими декартовыми координатами, они, обратив внимание на то, что никакие 3 мины не лежат на одной прямой, протянули специальный шнур от мины к мине так, чтобы он образовал выпуклый многоугольник минимального периметра, при этом все остальные мины оказались внутри многоугольника. Обезвредив соединенные мины, они вновь протянули шнур по тому же принципу, и опять обезвредили соединенные шнуром мины. Так продолжалось до тех пор, пока очередной шнур оказалось невозможным протянуть, руководствуясь изложенными правилами. Сколько мин осталось обезвредить и сколько раз саперам приходилось протягивать шнур?
Входные данные В первой строке входных данных записано целое число N (3 ≤ N ≤ 1000) – количество мин. Во второй строке записано 2 N целых чисел (N пар xi, yi), описывающих координаты каждой мины (−32000 ≤ xi, yi ≤ 32000). Выходные данные Выведите два целых числа через пробел - количество оставшихся мин и количество операций по натягиванию шнура. контрпример: 9 0 0 0 8 6 8 6 0 1 1 1 7 5 7 5 1 3 2 |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача минимизации дисбаланса на линии сборки (задача минимакса) | LenZab | Microsoft Office Excel | 13 | 13.03.2011 22:51 |
задача! | вредина123 | Помощь студентам | 3 | 16.12.2010 11:53 |
Задача. | Dantewac | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 11.12.2010 14:15 |
Задача на с++ | Екатерина Шпигель | Помощь студентам | 0 | 07.12.2010 08:52 |