Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Помещается ли один прямоугольник в другой

Автор: Анка 10.02.2004 8:48

Как определить, помещается ли прямоугольник A*B в прямоугольник С*D, если можно их поворачивать?
Например, 5*1 помещается в 5*1, 6*3, 4.3*4.3, но не помещается в 4*1, 10*0.5, 4.2*4.2.
Заранее спасиб всем, кто поможет.

Автор: P@sh@ 10.02.2004 16:00

думаю, сначала надо повернуть оба прямоугольника вертикально (т.е. поменять стороны местами, если нужно), далее:
1) если A>C, сразу выход - никак не войдет
2) если B<=D, тоже выход - вошёл и без поворотов
3) определяем минимальный необходимый угол поворота - точнее его косинус - просто поделив D на B - под этим углом прямоугольник влезает хотя бы по вертикали
4) складываем проекции сторон (B*sin+A*cos) - и сравниваем с C
собственно, всё... программа нужна ?

PS: кстати, получается, что 5x1 влазит в 4.3x3.4 (примерно)

Автор: Zerokul 10.02.2004 23:48

На сколько я понял пряпугольники в 2D, следовательно возьми не сравнивая их площади, а сравни их стороны. Есле одна из сторон основного прямоугольника меньше одной из сторон доугого(который должен войти или не войти) то второй не войдёт в основной wink.gif

Автор: Анка 11.02.2004 5:40

P@sh@, по-моему, все бы оно хорошо, но предлагаемый способ определения косинуса угла подходит не для прямоугольника, а для отрезка. Если я не так поняла, объясните, pls, еще раз.

Есть у меня некоторая идея. Если прямоугольник1 помещается в 2, то периметр2>=периметр1. В обратную сторону это утверждение не всегда действует.
Может быть тогда добавить условие: если хотя бы одна сторона прямоугольника 2 меньше обеих сторон прямоугольника 1, то 1 не помещается в 2.
Как думаете, хватает этих условий?

Автор: P@sh@ 11.02.2004 8:46

да, действительно, не довел мысль до конца, еще подумаю
Насчет периметров фиг знает, доказать бы как-то надо

Автор: P@sh@ 11.02.2004 8:58

поворачивать надо не сторону, а диагональ(так же, поделив D на нее), и проекции складывать три, а не две, т.е. удвоенная проекция малой стороны+проекция диагонали

Автор: Анка 11.02.2004 11:47

Насчет периметров доказывается через неравенство треугольника: сумма двух сторон больше третьей. Сотавляются по одному неравенству для четырех треугольников(которые отсекает маленький прямоугольник в большом), причем третьей стороной берется та, которая принадлежит маленькому прямоугольнику. Все это скаладывается и получается, что периметр маленького меньше периметра большого.  
Зря нельзя картинку прилепить, понятнее было бы и обьяснять легче...и спрашивать тоже...

Угол поворота диагонали к основанию не равен углу между меньшей стороной и вертикалью.

Автор: P@sh@ 11.02.2004 14:38

Угол поворота диагонали к основанию не равен углу между меньшей стороной и вертикалью.
значит надо еще вычислить угол между диагональю и B и добавить его к повороту

Автор: trminator 11.02.2004 17:26

Каритнку прилепить можно, только выкладывать нужно на своей страничке (если есть)