Есть набор окружностей на плоскости. Нужно построить фигуру, обладающую тремя свойствами:
она должна быть связной
она должна содержать все окружности
среди фигур, удовлетворяющих первым двум свойствам, она должна иметь наименьший периметр
По-моему, задача вполне достойна этого форума. Кстати, хотелось бы узнать полиномиальный алгоритм решения
Здравствуйте, m.a.g., Вы писали:
MAG> MAG>она должна быть связной MAG>она должна содержать все окружности MAG>среди фигур, удовлетворяющих первым двум свойствам, она должна иметь наименьший периметр MAG>
MAG>По-моему, задача вполне достойна этого форума. Кстати, хотелось бы узнать полиномиальный алгоритм решения
Здравствуйте, m.a.g., Вы писали:
A>Построение выпуклой оболочки?
MAG>А как ее строить? В смысле, с набором точек все понятно, но что делать с набором окружностей?
Для частного случая когда все радиусы равны должен подойти такой вариант. Строим выпуклую оболочку для точек-центров окружностей. Затем соседние окружности (их центры — соседние точки оболочки) соединяем касательными. Тогда решением задачи будет: дуга окружности, касательная, дуга другой окружности и т.д. Осталось обобщить до разных радиусов.
Здравствуйте, WeCom, Вы писали:
WC>Для частного случая когда все радиусы равны должен подойти такой вариант. Строим выпуклую оболочку для точек-центров окружностей. Затем соседние окружности (их центры — соседние точки оболочки) соединяем касательными. Тогда решением задачи будет: дуга окружности, касательная, дуга другой окружности и т.д. Осталось обобщить до разных радиусов.
Дыкть вся проблема-то как раз в разных радиусах Кстати, тогда строить выпуклую оболочку центров окружностей не пойдет.
Сначала огорчу тех, кто считает, что выпуклая оболочка центров может дать решение:
Здесь выпуклая оболочка центров даёт четыре маленьких окружности, и большая окружность "вылезет" за пределы оболочки, построенной по этим маленьким окружностям.
Без ограничения общности считаем, что никакая окружность не содержится ни в какой другой целиком (иначе мы можем просто удалить такие окружности и это не повлияет на решение). Алгоритм построения будет небольшой модификацией алгоритма построения ВО (выпуклой оболочки) по точкам. Сперва решим маленькую задачу: даны две окружности, найти точки соприкосновения общих касательных и окружностей, то есть найти точки y11, y12, y21 и y22 на рисунке. Эти точки можно найти, если найти угол $\alpha$, а его можно найти из того, что $\cos\alpha = \frac{r2-r1}{d(x1,x2)}$, где $d(x1,x2)$ — расстояние между точками (обычное, евклидово).
Теперь собственно построение: найдём окружность, которая гарантированно находится с краю, например, для которой первая координата минус радиус есть минимум. Пусть это будет окружность C1. Пусть L будет вертикальной касательной к окружности C1. (По смыслу L — это внешняя касательная к некоторым окружностям).
Перебираем все окружности, кроме С1, и для каждой окружности C вычисляем угол $\beta_2$, и точки y12 и y22; выбираем ту окружность, для которой угол $\beta_2$ минимален.
Чтобы не нарваться на угол $\beta_1$ вместо $\beta_2$ для прямой L нужно хранить направление обхода.
Если таких окружностей несколько, то среди таких окружностей выбираем ту, для которой расстояние $d(y12,y22)$ минимально. (Такое правило выбора гарантирует нам, что мы не вернёмся назад и не свернём вовнутрь). Получили окружность C2. Теперь прямую L положим как прямую, соединяющую точки y12 и y22. Если эти точки совпадают, то L не меняется.
Следующая итерация. Перебираем все окружности, кроме C2, для каждой вычисляем угол, точки и т.д. Получили окружность C3.
Второе решение чуть красивее, поскольку не изобилует частными случаями, но зато более трудоёмко с вычислительной точки зрения (хотя тоже полином).
По-прежнему считаем, что никакая окружность не содержится ни в какой другой целиком.
Перебираем все пары окружностей, и для каждой пары вычисляем точки y11, y12, y21, y22. Полученные точки помещаем во множество Y. Итого $|Y|=2(n-1)n$, где $n$ -- количество окружностей.
Теперь находим выпуклую оболочку множества $Y$. Получим вектор точек $V$.
Что представляет собой вектор $V$? Это будет последовательность пар точек, где каждая пара принадлежит какой-то окружности: $V = { y1i,y2i, y1j,y2j, y1k,y2k ... }$, где $y1i, y2i \in C_i$; $y1j, y2j \in C_j$; $y1k, y2k \in C_k$...
Всё, выпуклая оболочка практически построена: точки из одной пары соединяем соответствующей дугой окружности, точки из разных пар соединяем отрезком.
Здравствуйте, WeCom, Вы писали:
WC>Здравствуйте, m.a.g., Вы писали:
A>Построение выпуклой оболочки?
MAG>А как ее строить? В смысле, с набором точек все понятно, но что делать с набором окружностей?
WC>Для частного случая когда все радиусы равны должен подойти такой вариант. Строим выпуклую оболочку для точек-центров окружностей. Затем соседние окружности (их центры — соседние точки оболочки) соединяем касательными. Тогда решением задачи будет: дуга окружности, касательная, дуга другой окружности и т.д. Осталось обобщить до разных радиусов.
А для разных радиусов вполне подходит алгоритм оборачивания подарка, только в более зам##нной форме.
Здравствуйте, LCR, Вы писали:
LCR>Второе решение чуть красивее, поскольку не изобилует частными случаями, но зато более трудоёмко с вычислительной точки зрения (хотя тоже полином).
Тоже верно. Но я не упомянул — задача была предназначена для ACM-олимпиад по информатике с ограничением на 600k памяти. Просто не удалось бы хранить все точки для 1000 окружностей
Здравствуйте, m.a.g., Вы писали:
МAG>Но я не упомянул — задача была предназначена для ACM-олимпиад по информатике с ограничением на 600k памяти. Просто не удалось бы хранить все точки для 1000 окружностей
Кхе, кхе... Это... давайте возьмём 51201 окружность, и они не поместятся в эти 600k — усё, мы в глубокой луже
Здравствуйте, LCR, Вы писали:
LCR>Теперь собственно построение: найдём окружность, которая гарантированно находится с краю, например, для которой первая координата минус радиус есть минимум. Пусть это будет окружность C1. Пусть L будет вертикальной касательной к окружности C1. (По смыслу L — это внешняя касательная к некоторым окружностям).
LCR>Перебираем все окружности, кроме С1, и для каждой окружности C вычисляем угол $\beta_2$, и точки y12 и y22; выбираем ту окружность, для которой угол $\beta_2$ минимален.
LCR>Следующая итерация. Перебираем все окружности, кроме C2, для каждой вычисляем угол, точки и т.д. Получили окружность C3.
LCR>И так далее, пока снова не наткнёмся на С1.
Поскольку одна и та же окружность может учавствовать в обходе несколько раз, то этот критерий не подходит для завершения алгоритма. Полагаю, что итерации следует повторять до тех пор, пока вектор (y12, y22) не сделает полный оборот (2pi).
Здравствуйте, Дмитро, Вы писали:
LCR>И так далее, пока снова не наткнёмся на С1.
Д>Поскольку одна и та же окружность может учавствовать в обходе несколько раз, то этот критерий не подходит для завершения алгоритма. Полагаю, что итерации следует повторять до тех пор, пока вектор (y12, y22) не сделает полный оборот (2pi).
Точнее говоря, пока не выполнятся оба этих условия. Контрпример ко второму условию: последняя, первая и вторая окружности лежат на одной прямой и имеют одинаковые радиусы. Работа остановится за шаг до конца.
Здравствуйте, m.a.g., Вы писали:
Д>Поскольку одна и та же окружность может учавствовать в обходе несколько раз, то этот критерий не подходит для завершения алгоритма. Полагаю, что итерации следует повторять до тех пор, пока вектор (y12, y22) не сделает полный оборот (2pi).
MAG>Точнее говоря, пока не выполнятся оба этих условия. Контрпример ко второму условию: последняя, первая и вторая окружности лежат на одной прямой и имеют одинаковые радиусы. Работа остановится за шаг до конца.
Точно! Я почему-то это учёл при построении контрпримера, но забыл при построении алгоритма
Кстати, тогда строить выпуклую оболочку центров окружностей не пойдет.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
