Как определить, помещается ли прямоугольник A*B в прямоугольник С*D, если можно их поворачивать?
Например, 5*1 помещается в 5*1, 6*3, 4.3*4.3, но не помещается в 4*1, 10*0.5, 4.2*4.2.
Заранее спасиб всем, кто поможет.
думаю, сначала надо повернуть оба прямоугольника вертикально (т.е. поменять стороны местами, если нужно), далее:
1) если A>C, сразу выход - никак не войдет
2) если B<=D, тоже выход - вошёл и без поворотов
3) определяем минимальный необходимый угол поворота - точнее его косинус - просто поделив D на B - под этим углом прямоугольник влезает хотя бы по вертикали
4) складываем проекции сторон (B*sin+A*cos) - и сравниваем с C
собственно, всё... программа нужна ?
PS: кстати, получается, что 5x1 влазит в 4.3x3.4 (примерно)
На сколько я понял пряпугольники в 2D, следовательно возьми не сравнивая их площади, а сравни их стороны. Есле одна из сторон основного прямоугольника меньше одной из сторон доугого(который должен войти или не войти) то второй не войдёт в основной
P@sh@, по-моему, все бы оно хорошо, но предлагаемый способ определения косинуса угла подходит не для прямоугольника, а для отрезка. Если я не так поняла, объясните, pls, еще раз.
Есть у меня некоторая идея. Если прямоугольник1 помещается в 2, то периметр2>=периметр1. В обратную сторону это утверждение не всегда действует.
Может быть тогда добавить условие: если хотя бы одна сторона прямоугольника 2 меньше обеих сторон прямоугольника 1, то 1 не помещается в 2.
Как думаете, хватает этих условий?
да, действительно, не довел мысль до конца, еще подумаю
Насчет периметров фиг знает, доказать бы как-то надо
поворачивать надо не сторону, а диагональ(так же, поделив D на нее), и проекции складывать три, а не две, т.е. удвоенная проекция малой стороны+проекция диагонали
Насчет периметров доказывается через неравенство треугольника: сумма двух сторон больше третьей. Сотавляются по одному неравенству для четырех треугольников(которые отсекает маленький прямоугольник в большом), причем третьей стороной берется та, которая принадлежит маленькому прямоугольнику. Все это скаладывается и получается, что периметр маленького меньше периметра большого.
Зря нельзя картинку прилепить, понятнее было бы и обьяснять легче...и спрашивать тоже...
Угол поворота диагонали к основанию не равен углу между меньшей стороной и вертикалью.
Угол поворота диагонали к основанию не равен углу между меньшей стороной и вертикалью.
значит надо еще вычислить угол между диагональю и B и добавить его к повороту
trminator
11.02.2004 17:26
Каритнку прилепить можно, только выкладывать нужно на своей страничке (если есть)
Цитата(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 (примерно)
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста,
нажмите сюда.