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

Question

[Егор Трубников-Панов]

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

Пример:
Прямоугольник 960 на 500 пикселей,
есть 10 квадратов.
надо их впихнуть целиком в этот прямоугольник так чтобы они при этом были максимально возможного размера.

Comments

[Mrrl]

Вопрос к условию: слово "ровно" в формулировке вопроса не случайно? То есть, требуется ли, чтобы стороны квадратов были параллельны сторонам прямоугольника? В списке требований этого условия нет.
Потому что если квадраты могут располагаться под углом, то приведённые ниже решения неоптимальны. Например, для прямоугольника 120*120 и 5 квадратов они дадут ответ 40, хотя, повернув квадраты на 45 градусов, мы можем увеличить их размер до 42.42 пикселя.

Answer 1

[Rsa97]

Если не нужно полное покрытие прямоугольника, то общий алгоритм такой:
1. Считаем максимальную сторону квадрата = int(sqrt(высота_прямоугольника*ширина_прямоугольника/количество_квадратов)) = 219
2. Берём ширину и высоту, делим нацело на все числа от 1 до количества квадратов. Из полученного списка удаляем все числа, большие максимальной стороны квадрата, удаляем дубликаты и сортируем по убыванию.
(192, 166, 160, 137, 125, 120, 106, 100, 96, 83, 71, 62, 55, 50)
3. Для полученных размеров считаем количество квадратов, умещающихся в прямоугольник = int(высота_прямоугольника/размер_квадрата)*int(ширина_прямоугольника/размер_квадрата). Как только получаем число большее необходимого количества квадратов - останавливаемся.
n(192) = 10
Итого - сетка 5х2 со стороной квадрата 192 пиксела. По вертикали остаются 116 свободных пикселов.

Comments

[Егор Трубников-Панов]

решил так:
вычислил максимальный размер стороны квадрата sqrt(Площадь/количество)
присвоил это к X
и циклом пробежался в сторону уменьшения X
подставляя его в формулу
K=(ширина div X)*(высота div X)
пока K не станет равно количеству квадратов
получилось не так уж много итераций
при большом количестве квадратов вообще в два прохода выполняется.

Answer 2

[Армянское Радио]

Наибольший общий делитель длин сторон прямоугольника. Искать алгоритмом Евклида. Это будет сторона. А площадь найдется возведением в квадрат.

Comments

[Егор Трубников-Панов]

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

[Армянское Радио]

Егор Трубников-Панов: Тогда у вас будет задача на поиск минимума квадратичного функционала. J=a*b-K(a,b,l)*l*l
Здесь a и b - стороны прямоугольника.
K(a,b,l) - количество квадратов со стороной l, которое можно в этот прямоугольник поместить. Определяется как [a/l]*[b/l]; [] - округление вниз.
Решайте ее хоть прямым перебором по l от 0 до min(a,b); цель - найти такие l, чтобы J было минимальным. Это будут варианты длин.
Смысл J - величина незаполненной площади.

Answer 3

[Пума Тайланд]

Наибольший общий делитель даст размер стороны квадрата