Добрый день.
Прошу помощи в решении одной хитрой задачи.
Описание 1. Художественное.
Есть плоская поверхность квадратной формы (стол) шириной N. Требуется вычислить, сколько максимально возможно разместить квадратов (например, обложек от пластинок) со стороной S (S < N) так, чтобы центр масс каждого квадрата находился на поверхности (обложки не упали со стола). При этом квадраты не должны перекрывать друг друга, но их можно вращать.
Описание 2. Геометрическое.
Есть плоская поверхность квадратной формы шириной N. На ней могут быть размещены под любым углом параллельные равноудаленные друг от друга на расстояние S прямые. Требуется найти максимальное число, которое можно получить сложением количества прямых, попадающих в плоскость и количества отрезков длины S, которые можно разместить на участках прямых, лежащих на плоскости
Решение (очевидное, но неоптимальное).
Разместить линии на плоскости, при этом линия должна пересекать угол фигуры.
Вращать их с минимальным шагом вокруг угла фигуры, каждый раз пересчитывая искомое значение.
Сместить точку пересечения линии и угла вдоль края фигуры на минимальное значение.
Повторять пункты 2 и 3, пока смещение в пункте 3 не достигнет S.
Проблема.
Смещение происходит на дискретный угол / шаг, поэтому всегда есть вероятность пропустить максимум из-за недостаточной точности. Например, при S = 24 и N = 186 используя угол в интервале 20,839-20,905 градусов можно разместить 69 квадратов (или 58 отрезков на 9 линиях, плюс 2 линии без отрезков)