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