Более понятная формулировка. Есть столбики одинакового радиуса. Надо найти минимальную длину веревки, которой можно обтянуть все столбики так, чтобы ни один не остался снаружи.

Примечание. Предполагается активное использование массивов.

Моя голова сломалась    .

Надо превратит круги в точки, и решить задачу для точек - центров окружностей, потом добавить к нему 2*pi*r, и
получится ответ.
А задачу для точек надо решить методом построения выпуклой оболочки

Всё так, только непонятно, как в условии согласуется "N-угольник" и "кривая" - это же разные вещи.

Если действительно разрешена произвольная кривая, то метод aram90 правильный. Хотя я когда-то решал эту задачу, и до идеи с 2 pi r не дошёл, и где-то часа полтора писал эту геометрию со всякими дугами, секторами окружностей... 

  Скажем так: "кривой" я назвала это потому, что это будет не прямая, а совокупность отрезков прямых (т.е. самый настоящий N-угольник в полном смысле этого слова).2*pi*r - полная длина окружности... А у нас веревка будет соприкасаться лишь с частью столбика (выделено красным на рисунке).
(или это компенсируется засчет того, что центр окружности (случай с точками) находится "дальше", чем сам окружность?
Пока у меня тоже получается эта страшная геометрия...
Это зеркало! Я просила дописать к началу названия зеркала "[Алгоритм]" - внимательный админ сказал, что это, к сожалению, невозможно.

Добавлено через 2 минуты и 17 секунд
А вообще изначально тема была создана в разделе "Алгоритмы" ->  отсутствие "[Алгоритм]" в начале названия хорошо компенсировалось подписью внизу "Зеркало из раздела "Алгоритмы".

KasMP, вот точно такая же задача: http://acm.timus.ru/problem.aspx?space=1&num=1020

Я её решил так(за кривость не ругать, тут был важен только результат):



То есть по уравнению прямой находим сначала расстояния для точек, а потом прибавляем 2*Pi*R как уже было сказано.
Timus сказал что решено верно))

THandle, очень рада твоему участию    !

Твой код решает задачку с Timus-а, это бесспорно  (даже ностальгия по паскалю проснулась  , пока просматривала...).
Но моя задачка и задачка с Timus-а - отнюдь не одно и то же  :
Т.е. у Timus-а то, как веревка обтягивает шляпки/столбики/деревья/окружности (другими словами, как построен многоугольник), уже определено. А у меня нет  .

Моя основная проблема как раз и состоит в том, что я не знаю (пока), как выбрать правильную последовательность вершин (самая правильная та, которая требует самую короткую веревку). Впрочем, надо изучить метод построения выпуклой оболочки  , рекомендованный aram90 (по названию это походит на то, что нужно).
Задачку с Timus-а я бы решила без проблем сама - сложить длины отрезков несложно  .

Тем не менее, от задачки с Timus-а есть большая польза  : я убедилась, что действительно можно сначала рассматривать точки, а потом просто прибавить длину окружности  (только пока не поняла, как это доказать...).

Добавлено через 1 минуту и 3 секунды

Большое спасибо за наводку , посмотрю  ...

KasMP, какое-то хитрое условие 
Но раз получается, что "окружать" сами столбики мы не должны, т.е. дуг не надо, то получается, что 2 Pi R действительно прибавлять не надо, а сама искомая кривая будет представлять собой многоугольник, причём выпуклую оболочку центров окружностей (в этом легко убедиться, достаточно сдвинуть каждый отрезок к центрам обеих окружностей; т.к. в точке касания радиус перпендикулярен отрезку, то никаких "компенсирований" не будет).

Ну а выпуклая оболочка - вообще стандартная вещь.
Например, вот: e-maxx.ru/algo/convex_hull_graham 

Видимо, я совсем разучилась объяснять...Окружать столбики как раз надо , дуги надо учитывать обязательно   !

Еще условие можно сформулировать так  :


Добавлено через 2 минуты и 24 секунды

Спасибо за ссылочку  .
Я вчера нашла другую, где описывается не только метод Грэхема, но и метод Джарвиса    .

Ну раз окружать таки надо, то и прибавлять 2 pi r надо тоже 
Откуда это берётся - оттуда, что если мы рассмотрим все столбики (не считая тех, что не в выпуклой оболочке), то в сумме эта кривая "накрутит" дуг как раз на полные 360 градусов, т.е. ровно на одну длину окружности. В этом можно убедиться, если мысленно удалить все прямые отрезки кривой, как бы совместив все столбики в один - как раз все дуги кривой сложатся и образуют одну окружность.


Если ограничения маленькие, то можно и Джарвиса. Хотя мне всегда казалось, что Грэхэм пишется проще, да и асимптотически в общем случае он лучше.

Итак, алгоритм я полностью поняла  , за что вам большое спасибо  .
Рано или поздно я все это реализую и покажу вам результат  .

К слову, maxdiver, у тебя очень хорошая ссылочка  - написано коротко, емко и понятно  , без лишних доказательств очевидного, без ... .

Я нелепо споткнулась на самом неожиданном месте, на поиске самой нижней (правой) точки.
У меня 2 функции:

• LowermostRightPoint.
  По сути, непосредственно оценками она не занимается, она просто помнит текущую лучшую точку и подкидывает новые точки функции PresentFirstPoint, которая и выполняет всю оценивающую работу (короче можно сказать, что LowermostRightPoint координирует действия, выполняет административную функцию).
• PresentFirstPoint.
  Она получает:
  • ссылку на массив с координатами;
  • индекс точки, которую нужно сравнить с лучшей текущей (i);
  • индекс текущей лучшей точки (res).
  Сначала она смотрит, меньше ли ордината текущей точки, чем ордината лучшей точки. Если меньше, то, естественно, ты запоминаем номер текущей точки как лучший.
  Если не меньше, то проверяем, а не совпадают ли ординаты. Если совпадают, то более чем логично сравнить абсциссы... Лучшая точка та, у которой абсцисса больше.
  Потом  PresentFirstPoint возвращает в своему руководителю LowermostRightPoint номер лучшей на данный момент точки.

По-моему, все идеально. Но работает, как хочет... То правильно, то выбирает правейшую (нижнюю) точку, то вообще левую верхнюю    .





Добавлено через 4 минуты и 31 секунду
Если кто-то решится помочь, то следующее - для вашего удобства  ...





Добавлено через 7 минут и 18 секунд
Еще быстрая сортировка не сортирует точки в порядке увеличения угла (уменьшения косинуса) массив... Но уж с этим я должна разобраться!!!!!!!!!

KasMP, ох... C++... 

Покажи то описание по которому ты пишешь алгоритм. Я попробую сначала на Паскале сделать, а потом перевести... Задачка интересная. 

Еще, чтобы не возникало подобных тем:
http://forum.vingrad.ru/forum/topic-230265.html

Я сделал зеркало на эту тему во флейм(пока на неделю). Если против этого зеркала имеешь что-то - сразу удалю 

Вот  .

Ок, больше не буду   .

Удали, пожалуйста  .

Добавлено через 8 минут и 44 секунды
Вообще говоря, остальные части алгоритма у меня написаны и должны работать (по крайней мере, на мини-тестиках выполнялись правильно).

А вот с на первый взгляд легкой задачкой определения самой нижней (правой) точки творится что-то нереальное! Вот где у меня ошибка? Я прогоняла на бумажечке разные значения всего - все правильно. Может быть, ошибка в каких-то конкретно моих настройках?

Да я не против  Просто кажется что никто в такие темы не заходит/не переходит по ссылкам.



Ок.


В общем - делаю сейчас прожку. Для наглядности все точки выводим в виде рисунка на экран(типа как в описании алгоритма).
Получилось найти первый элемент и отсортировать массив. Остальное буду пробовать сделать вечером...

Напишу заголовки моих функций (вдруг ты решишь организовать свои подобным образом  - будет проще сравнивать  )...



Добавлено через 48 секунд

Как показывает опыт, переходят и даже думают (а иногда де отвечают)  !

Спасибо  .