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

[Utkin]

Вот рисунок. Красная область показывает, то что я описал выше. Далее мы рассматриваем только часть прямоугольника с белой областью.

[evg_m]

Вот рисунок. Красная область показывает, то что я описал выше. Далее мы рассматриваем только часть прямоугольника с белой областью.

вот рисунок показывающий, что это не всегда годится.
11.jpg

[Utkin]

Очень даже годится. По условию круги могут распологаться где угодно в рамка прямоугольника. Так что пока не вижу никаких противоречий.

[evg_m]

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

[Utkin]

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

[LeBron]

Задача довольно интересная. Что-то отсекать явно не катит...tunyash, даже решение за биквадрат, как я понял, "не до конца стопроцентно" работает. Или у Вас есть строгое решение за N^4?

[Utkin]

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

Что-то отсекать явно не катит...

Аргументы против? Моя идея немножко коряво выражена, но имеет рациональное зерно.

[evg_m]

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

скорее всего следует читать БЕЗ НАЛОЖЕНИЯ друг на друга.
т.е. круглые диски на прямоугольной площади в ОДИН слой.
Но возможно я не прав.
иначе упорядочиваем по размеру и складываем пирамидой от большого к малым.
Одинаковые не пересекаются, у них всего лишь общая граница.

[LeBron]

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

Аргументы против? Моя идея немножко коряво выражена, но имеет рациональное зерно.

Может, я неправильно понял, но если имеется ввиду "для каждого круга отрезать от прямоугольника квадрат, сторонами которого являются касательные к кругу, и дальше решать для остатка", то не идет - можно, допустим, взять круг и квадрат с равностью сторон (т.е стороны и диаметра) и немного мелочи, и тогда мы все отрежем еще для первого круга, хотя "по углам", возможно, еще влезет "мелочь".

Если иначе - можно более доступно объяснить?
Хотя ладно, а то я так и не понял, с кругами задача или с окружностями) С кругами она очень интересная)

[Utkin]

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