Найти длинну кривой

[vlad_light]

Даны $N$ кругов с центрами в точках $(x_i,y_i), i=1,2,...,N$ и радиусами $r_i, i=1,2,...,N$ соответственно. Вокруг кругов натянута леска. Нужно быстро (с точки зрения сложности) посчитать её длину.
(Будем считать, что леска касается как минимум один раз к каждому кругу и множество, которое она ограничевает является выпуклым).
Подскажите идею... Спасибо!

[ИСН]

Что значит "касается как минимум один раз к каждому кругу"? Значит ли это, что лишних кругов гарантированно нет? что convex hull искать не нужно? что известна последовательность, в которой леска касается кругов? а то ведь если неизвестна - то она может быть чертовски не-единственной!

-- Ср, 2012-09-19, 17:05 --

Ах, ещё и выпуклым. То есть нам гарантируют, что круги расположены хорошо, так что в convex hull входят они все. Ну тогда и думать нечего: берём и идём по ним, один за другим. Длина дуги, длина касательной. Следующий. Быстрее никак.

[Shtorm]

vlad_light в сообщении #620966 писал(а):

... леска касается как минимум один раз к каждому кругу...

Так леска что, может касаться несколько раз одного и того же круга? То есть леска может быть обмотана несколько раз (а может и в несколько слоёв) вокруг выпуклого множества???

[Профессор Снэйп]

Надо бы в заголовке темы грамматическую ошибку поправить, а потом саму тему в "Computer Science" перенести. А затем уточнять: в каком формате заданы координаты и радиусы кругов, какая точность вычислений требуется, какое время допустимо, какова точная формулировка ограничений, которым удовлетворяют исходные данные...

[vlad_light]

Цитата:

Ах, ещё и выпуклым. То есть нам гарантируют, что круги расположены хорошо...

В условии задания подразумевалось, что круги расположены хорошо, а про выпуклость и касание я дополнительно сам додумал. В оригинале задачка формулировалась так:
мне на листке бумаги рисуют 4 круга, говорят, ты знаешь координаты центров и радиусы всех кругов. Вокруг них обмотана леска, нужно найти её длину. Первое, что пришло в голову -- это

Цитата:

Длина дуги, длина касательной. Следующий.

Но тут сразу же пошли возражения, типа, это ответ первоклассника, нужно что-то по-быстрее... После вопроса "Программировал ли я что-то самостоятельно?" наша беседа окончилась

Цитата:

что convex hull искать не нужно

Скорее всего именно это и имелось ввиду. Спасибо ИСН за подсказку, буду изучать эту самую convex hull. Ещё раз спасибо!

Цитата:

Так леска что, может касаться несколько раз одного и того же круга? То есть леска может быть обмотана несколько раз (а может и в несколько слоёв) вокруг выпуклого множества???

Допустим, леска обмотана 100500 раз вокруг каждого круга и "over 9000" раз вокруг выпуклого множества . Как это влияет на ход решения задачи?

(Оффтоп)

Цитата:

Надо бы в заголовке темы грамматическую ошибку поправить

Очепятка

Цитата:

саму тему в "Computer Science" перенести

Уже понял, спасибо!

Цитата:

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

Как уже говорил, ничего точно задано не было. Задача была в стиле "знаешь/не знаешь".
Всем спасибо!

[Shtorm]

vlad_light в сообщении #621009 писал(а):

Допустим, леска обмотана 100500 раз вокруг каждого круга и "over 9000" раз вокруг выпуклого множества . Как это влияет на ход решения задачи?

Если подходить к задаче в том смысле, как она была сформулирована в первом сообщении - то от этих дополнительных условий напрямую зависит вычисляемая длина лески. А если по принципу знаешь, не знаешь, то конечно кроме дополнительных коэффициентов ничего значимого.

[gris]

Вот бы радиусы были одинаковы. Тогда можно вычислить только периметр многоугольника и добавить длину дуги круга. Для четырёх — длину окружности.

[Утундрий]

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

[ИСН]

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

[vlad_light]

(Оффтоп)

Цитата:

от этих дополнительных условий напрямую зависит вычисляемая длина лески

Вы что-то по существу хотите сказать или так просто троллите? Для меня пока неочевидно, как решение задачи изменится...

Цитата:

Вот бы радиусы были одинаковы. Тогда можно вычислить только периметр многоугольника и добавить длину дуги круга. Для четырёх — длину окружности.

А почему именно для четырёх? Если взять 3 окружности, центры которых лежат на одной прямой. Тогда ведь тоже нужно взять периметр + длину круга?

[Утундрий]

За длинноту не скажу, но вот ежели к примеру пройтись по полному обороту $\theta$ с достаточно мелким шагом, $\mathop {\max }\limits_i \left( {y_i \cos \theta - x_i \sin \theta + r_i } \right)$ вычисляя, да $i$ на которых он достигается аккуратно в строку записывая... Останется только для каждой такой пары расстояния от внешней касательной до всех "не засветившихся" повычислять, с радиусом сравнить, да и адаптнуть сколько понадобится в нехороших случаях. И сызнова... Когда-нибудь да сойдётся.

[gris]

vlad_light, конечно, для любого количества кругов равного радиуса добавляется длина окружности. Надо лишь следить за последовательностью обхода при вычислении периметра. Но для разных радиусов чего-то не могу придумать. Ну точки касания не обязательно находить. Длины касательных считаются по теореме Пифагора через расстояния между центрами и разности радиусов, дуги через углы. Но в маленькую формулу это не сворачивается. Разве что оценки сверху-снизу получить.

[vlad_light]

Спасибо, gris! А Вы можете дать идею доказательства того факта, что для любого кол-ва кругов равного радиуса, сумма частей лески, которые натянуты на круги равна длине одного круга.

[_Ivana]

При $n$ окружностях одинакового радиуса все внешние касательные параллельны линиям соединяющем центры, прямые отрезки периметра по касательным равны отрезкам между центрами, а суммарный угол всех окружностей где леска проходит по каждой окружности равен $2pi$ - потому что радиусы к точкам касания также параллельны и при последовательном проходе по всем окружностям каждый раз арифметически добавляется определенный угол, и при завершении обхода получаем наши $2pi$. Простите за возможно сумбурное изложение, но надеюсь будет понятно, что я имел в виду.

[Утундрий]

vlad_light в сообщении #621265 писал(а):

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

Прочто выбросьте все прямолинейные отрезки и перенесите (без вращения!) все круги в какой-нибудь один.