Геометрия. Влезут ли окружности в прямоугольник.

[tunyash]

Доброго времени суток. Я еще не студент, но надеюсь, что меня простят.
Задача формулируется так:
Есть n кругов с заданными радиусами и прямоугольник со сторонами w и h. Требуется узнать влезут ли все круги одновременно в прямоугольник без пересечений между собой и со сторонами прямоугольника.
Виноват, перепутал круги и окружности.
Возможно ли достичь асимптотики n^2? Можете поделиться идеями? Заранее спасибо.


Собственно моя идея. Сведем задачу к запихиванию одного круга в систему из прямоугольника и некоторого количества уже лежащих в нем кругов. Вставим круг в случайную точку внутри прямоугольника. После этого будем для некоторого круга искать другие круги, пересекающиеся с ним и выталкивать их из него. Затем сделаем то же для вытолкнутых кругов. Если круг оказался вытолкнут за пределы прямоугольника, то он ставится на границу и выталкивает из себя все круги. Если после того, как процедура запущена от n^3 кругов можно с большой долей вероятности утверждать, что вставить круг было невозможно. Асимптотика N^4.

[Utkin]

Как-то все заумно. Окружность влезет в прямоугольник только в случае если ее диаметр меньше самой меньшей из сторон прямоугольника. Остальные окружности влезут если они имеют меньшие диаметры, чем диаметр самого большой, помещающейся в прямоугольник окружности. Как-то так, при условии что я правильно понял задание и что оно здесь правильно описано. Нафига случайная точка? Точка известна - она является центром наибольшей окружности, при желании можно вычислить и для прямоугольника.
Собственно возникает вопрос - Причем здесь программирование?

[Don Karleone]

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

[Utkin]

Ну как частный случай, если все окружности разных диаметров + все что описано выше, то поместятся все .

[Stilet]

Нужно просто посчитать площади окружностей и площадь прямоугольника.

[tunyash]

Площади считать нельзя. Например, если у нас прямоугольник 1х1000000 и окружность радиуса 2. Площадь прямоугольника будет больше, но окружность не влезет в него.

Сообщение от Utkin

Ну как частный случай, если все окружности разных диаметров + все что описано выше, то поместятся все .

Да, вы правы. Я перепутал круги и окружности.
Извиняюсь за два поста подряд.

[Stilet]

Не я не так выразился.
Я это имел ввиду:http://ru.wikipedia.org/wiki/%D0%9A%...83%D0%B3%D0%B0

[tunyash]

Сообщение от Stilet

Не я не так выразился.
Я это имел ввиду:http://ru.wikipedia.org/wiki/%D0%9A%...83%D0%B3%D0%B0

Поясните, пожалуйста, при чем здесь?

[Utkin]

Я же Вам практически дал решение . Вот этот частный случай отсекаем от прямоугольника и получаем новый прямоугольник. В него по описанному Выше алгоритму пытаемся запихнуть оставшиеся круги и дело в шляпе. Если круги еще остались значит отсекаем снова пока прямоугольник не кончиться совсем.
Повторяю свой вопрос - причем здесь программирование?

[tunyash]

Сообщение от Utkin

Я же Вам практически дал решение . Вот этот частный случай отсекаем от прямоугольника и получаем новый прямоугольник. В него по описанному Выше алгоритму пытаемся запихнуть оставшиеся круги и дело в шляпе. Если круги еще остались значит отсекаем снова пока прямоугольник не кончиться совсем.
Повторяю свой вопрос - причем здесь программирование?

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