Есть круг радиусом R и квадрат с длиной стороны X.
Вопрос: сколько данных квадратов уместится внутри круга, при условии, что ни один квадрат не должен выходить за границу круга или накладыватся на другой квадрат.
P.S. Разумеется, квадраты нельзя мять, резать и пр.
Здравствуйте, Wind, Вы писали:
W>Есть круг радиусом R и квадрат с длиной стороны X.
W>Вопрос: сколько данных квадратов уместится внутри круга, при условии, что ни один квадрат не должен выходить за границу круга или накладыватся на другой квадрат. W>P.S. Разумеется, квадраты нельзя мять, резать и пр.
Задачи о т.н. "раскрое листа фанеры", когда на некоторой фигуре нужно разместить максимальное кол-во других фигур, имеют переборное решение (если я не ошибаюсь). Тут условия более частные, но тем не менее.
Здравствуйте, Umaxik, Вы писали:
U>Задачи о т.н. "раскрое листа фанеры", когда на некоторой фигуре нужно разместить максимальное кол-во других фигур, имеют переборное решение (если я не ошибаюсь). Тут условия более частные, но тем не менее.
Не уверен на счет сложных фигур, но в данном случае ошибаетесь. Для данной задачи ответ — конкретная формула.
Здравствуйте, Wind, Вы писали:
W>Есть круг радиусом R и квадрат с длиной стороны X.
W>Вопрос: сколько данных квадратов уместится внутри круга, при условии, что ни один квадрат не должен выходить за границу круга или накладыватся на другой квадрат.
W>P.S. Разумеется, квадраты нельзя мять, резать и пр.
Может кто логику увидит... у меня не получается.
X > R*Sqrt(2) -> 0
X <= R*Sqrt(2) -> 1
X <= 2*R/Sqrt(3) -> 2
X <= 4*R/Sqrt(29) -> 3
X <= R/Sqrt(2) -> 4 или более
Вообще, слабо верится в существование формулы. В любом случае, она будет сложная.
Могу сказать, что
Здравствуйте, 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).
К>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))
А как доказать, что надо рассматривать только 2 варианта сдвига: на 0 и Х/2?
Здравствуйте, Umaxik, Вы писали:
К>>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))
U>А как доказать, что надо рассматривать только 2 варианта сдвига: на 0 и Х/2?
Боюсь, что никак, т.к. при X = 4*R/sqrt(29) можно уложить 3 квадрата пирамидкой. И сдвиг будет на загадочную величину 3*X/16.
Здравствуйте, Tan4ik, Вы писали:
U>>А как доказать, что надо рассматривать только 2 варианта сдвига: на 0 и Х/2?
T>Боюсь, что никак, т.к. при X = 4*R/sqrt(29) можно уложить 3 квадрата пирамидкой. И сдвиг будет на загадочную величину 3*X/16.
На самом деле, всего существует конечное число величин сдвига, порядка O(N).
Пусть круг лежит на бумаге, разлинованной по горизонтали (с интервалом в X).
То есть он нарезан на полоски, в каждую из которых можно вписать некое количество квадратов, плюс останется слева и справа по как-бы-трапеции (два основания, вертикаль и дуга). И еще могут быть две неполноценных полоски (хорда-основание + дуга). Далее мы их игнорируем.
Если круг в нижней точке касается линии, то нижняя полоска вмещает 0 квадратов (очевидно). Сместив круг немного вниз (можно привести формулу, но это неважно), мы сможем вписать в нее 1 квадрат. Потом еще ниже — 2 квадрата...
То есть количество квадратов на k-й полоске Q[k] — это ступенчатая функция от величины сдвига y. Причем сдвиг варьируется в пределах Y/2, где Y = R — X*[R/X] -- остаток от деления нацело R/X.
Общее число квадратов в круге, Q(y) = sum[k=1..N] Q[k](y)
Это также ступенчатая функция.
Самая верхняя граница числа ступенек — это N*(N+1) (Q[k] = 0..N на каждой полоске). Реально, конечно же меньше: чем ближе полоска к центру круга, тем меньше у нее ступенек, учитывая, что люфт y=0..Y/2.
Мне кажется (хотя теоретически обосновывать сейчас затруднюсь), что будет не более N ступенек.
Получили несложную переборную задачу.
Q[k](y) -- число квадратов в полоске, на высоте H[k]=k*X+y от нижней точки круга (или, соответственно, между R-H[k] и R-H[k]-1 от центра).
Здравствуйте, Кодт, Вы писали:
К>На самом деле, всего существует конечное число величин сдвига, порядка O(N).
[skiped] К>Получили несложную переборную задачу.
Это действительно так, если верно утверждение:
К>0. Наиболее плотная упаковка квадратов — когда они образуют сетку по горизонтали (например). Потому что если К>некоторые квадраты повернуты или отодвинуты — около них образуется зона отчуждения, то есть бесполезная площадь.
Попробую объяснить почему мне оно очевидным не кажется.
К>Пусть круг лежит на бумаге, разлинованной по горизонтали (с интервалом в X). К>То есть он нарезан на полоски, в каждую из которых можно вписать некое количество квадратов.
Пусть мы нашли оптимальный сдвиг y, решив "несложную переборную задачу".
Теперь рассмотрим операцию "смещение вниз": "взять две соседние полоски (A — верхняя, B — нижняя), раздвинуть их путем смешения всех полосок ниже A на величину dy вниз". Также можно определить операции "смещение вверх" и "поврот смещенных полосок".
Мы выбирали y путем "упирания" квадратов одной из полосок. Остальные же квадраты достаточно свободны. Не сможем ли мы выкроить где-нибудь местечко под еще один квадрат, стороны которого не будут параллельны ни одной из полосок?
Итак:
Вычисление результата по данному алгоритму производится до значения j (обозначим это значение как j`), при котором L[j`+1]<=0.
L[0] = (2R – ∆X/2)
L[j] = L[j-1] – ∆X (4)
m[0] = L[0]/∆X – L[0]%∆X
m[j] = m[j-1] + 2*( L[j]/∆X – L[j]%∆X)
где: L[j] – длины соответствующих секущих
R – радиус подложки
m[j] – количество узлов определенных на соответствующей итерации алгоритма
% — операция взятия остатка от деления
[] — индекс (к сожалению не знаю как буквы делать нижним индексом)
Перекуём баги на фичи!
