Необходимо придумать алгоритм для определения, можно ли поместить в данную трапецию данные прямоугольник и окружность
Всем привет, учусь в ВУЗе, делаю лабу по основам алгоритмизации, попал в тупик.
Задача звучит так:
Мише необходимо склеить коробку с круглым дном (без крышки) заданных размеров. У него есть кусок картона трапецевидной формы. Помогите Мише ответить на вопрос – «Удастся ли ему склеить коробку?»
У меня есть некоторые идеи, но они к сожалению не сработали, сколько я не ломал голову.
Был бы очень рад обсудить идеи и решение задачи.
Ответы (2 шт):
Теорема Бойяи — Гервина – любые два многоугольника равной площади равносоставлены. То есть, первый можно порезать на куски, из которых составляется второй.
Пусть трапеция имеет площадь большую чем площадь нашей будущей коробки. Отрежем от трапеции кусок по площади равный боковой поверхности коробки, разрежем его и составим боковую поверхность.
Оставшая часть трапеции по площади превосходит круглое дно коробки. Опишем вокруг круга правильный многоугольник меньший по площади, чем остаток. Это всегда возможно, так как с возрастанием числа сторон описанные правильные многоугольники стремятся по площади к кругу. Отрежем от остатка трапеции лишнюю площадь, составим из куска правильный многоугольник, края обрежем, получится круг.
Коробка готова.
Вряд ли Миша слышал про Бойяи и, тем более, про Гервина. Поэтому из трапеции нужно вырезать прямоугольник и круг.
Итак, на входе имеем длины строн трапеции (что однозначно, возможно, с точностью до зеркального отражения, задаёт трапецию), высоту коробки и диаметр её дна (именно диаметр, а не радиус, так как размеры вещи всегда описываются её габаритами - размерами описанного трёхмерного прямоугольного параллелепипеда, но это не суть). Соответственно, выкройкой боковой стороны коробки будет прямоугольник "πd * h".
Нужно начинать с круга, потому что прямоугольник потом может занимать различное положение, а не только паралллельное одной из сторон (у круга с этим проще :-), как ни крути). Если трапеция достаточно большая, то круг может занимать в ней четыре крайних положения. По мере уменьшения соотношения размеров количество размещений сокращается.
Потом остаётся разместить прямоугольник в оставшейся части. Там тоже будут варианты, но они легко просчитываются.
P. S. Предлагаю подойти к задаче немного с другой стороны. Вариантов взаимного расположения круга и боковой части всего два (вместо прямоугольника д. б. параллелограмм, просто Paint его не рисует):
Круг может перемещаться вдоль стороны. Теперь нужно просто вписать эту конструкцию в трапецию.