Здравствуйте, Wind, Вы писали:

U>>Задачи о т.н. "раскрое листа фанеры", когда на некоторой фигуре нужно разместить максимальное кол-во других фигур, имеют переборное решение (если я не ошибаюсь). Тут условия более частные, но тем не менее.

W>Не уверен на счет сложных фигур, но в данном случае ошибаетесь. Для данной задачи ответ — конкретная формула.

Не жди аналитической формулы...

Примерный ход рассуждений:

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

1. По горизонтали в круг (вдоль диаметра) можно напихать примерно N=floor(2R/X) квадратов (точнее — нужно учесть толщину этой полоски из квадратов, так что 4*R^2 >= X^2*(N^2 + 1/4). N = floor(sqrt(4*R^2/X^2 — 1/4)).

2. Эта полоска может либо быть центрами квадратов на диаметре круга, либо смещена по вертикали на величину до X/2.
Пусть она на диаметре. Тогда общее число квадратов будет
Sum[k=-floor(N/2);+floor(N/2)] floor(sqrt(4*R^2/X^2 — (k+1/2)^2)

Если же она смещена на X/2, то
Sum[k=-floor(N/2);+floor(N/2)] floor(sqrt(4*R^2/X^2 — k^2))

Вроде бы ничего не напутал. (Разве что границы суммирования нужно уточнить; либо считать, что sqrt(-n)==0).