Как узнать, что из двух прямоугольников {A;B} и {a;b} один можно вложить в другой (так, чтобы любая точка одного лежала внутри другого)?
GD Star Rating
loading...
loading...
Как узнать, что из двух прямоугольников {A;B} и {a;b} один можно вложить в другой (так, чтобы любая точка одного лежала внутри другого)?
похожие публикации
неужели проверкой неравенств координат?
Уточню условие.
1. Прямоугольники заданы шириной и высотой.
2. Положение на плоскости любое.
ну дык показатели одного (w; h) меньше или равны показателям другого.
если бы всё было так просто. Еще раз, положение на плоскости любое.
ну и что? да хоть где угодно в пространстве. Если заданы только ширина и высота, то фиолетово. Подходят пор размерам, значит можно вложить. Что не так то? Либо условие неполное.
тогда что значит «подходят пор размерам»?
(a <= A && b <= B) || (a <= B && b <= A)
это неверно, подумайте еще.
Чегото ты явно не договариваешь.
всё сказал, или чтото непонятно?
и какие преобразования допустимы для вложения?
что ты называешь шириной и высотой?
A=|AB|, B=|BC| (красненьким мои обозначения у ABCD).
любое положение на плоскости значит
1. параллельный перенос;
2. поворот.
ну, sign(aA) == sign(bB) || sign(aB) == sign(bA)
не, фигню написал.
(aA)(bB) >=0 | (aB)(bA) >= 0.
я понял, почти тоже самое. Это слишком «строгое» условие. Неверно. Почитайте комментарии ниже: возможно, они подскажут решение.
а, понялпонял :
да, это тоже мимо.
разве это не было написано выше?
фактически, я так понимаю, что возможны два варианта
а) можно расположить параллельно
б) можно вдоль диагонали
Я думаю что это даже можно доказать через какиендь минимумы. Сейчас попробую:
Ось координат сейчас расположим по внешнему прямоугольнику ( который для проверки) {A,B}
если взять угол alha пока произвольный, то
нам необходимо условие, чтобы две проекции были меньше A и B
a sin( alpha)+b cos(alpha) <= B,
a cos( alpha) + b sin( alpha) <=A
не совсем, но полюбому неверно.
Пусть внешний прямоугольник имеет стороны A и B, внутренний a и b
У нас три варианта развития событий:
1. (a–A)(b–B) >=0 | (a–B)(b–A) >= 0 можно
2. Диагональ «внутреннего» прямоугольника больше диагонали «внешнего» тогда точно нельзя
3. ни одно из первых двух условий не выполнено. Тогда, возможно, «внутренний» прямоугольник можно вставить во «внешний», предварительно повернув. Не нарушая общности, будем считать, что B>=A и b>=a. Так как первое условие не выполнено, то «внутренний» прямоугольник можно расположить так, чтобы две его вершины лежали на сторонах «внешнего», см. картинку.
Теперь немного выкладок.
c=sqrt(a^2+b^2)
*=c^2A^2
Проведём линию, параллельную стороне A так, как показано на рисунке. Пусть точка пересечения этой линии со стороной b делит её в отношении l к m, а сторону в отношении k к n.
Блин, нужно было вершины както обозначить, ну ладно.
a/k=*/l, так как эти треугольники подобны. По той же причине, a/m=*/n.
По теореме Пифагора, m^2=a^2+a^2/*^2)*(*^2+l^2):a^2/*^2)*(*^2+(Am)^2).
Домножаем на *^2, раскрываем скобки справа, переносим всё влево, имеем:
(*^2A^2)*m^2+2*A*a^2*ma^2(*^2+A^2)=0
Это квадратное уравнение на m решайте сами, после его решения получим все стороны маленького треугольника a, k и m.
Теперь, по теореме о высоте прямоугольного треугольника, h=a*k/m.
Достаточным условием того, что «внутренний» прямоугольник помещается во «внешний» является неравенство 2h+*
то есть,
*=sqrt(c^2–A^2)
и
m^2=a^2+k^2 равно (a^2/*^2)*(*^2+l^2) равно (a^2/*^2)*(*^2+(A–m)^2), парсер лох
Я решал эту задачу девять лет назад на вступительных экзаменах в десятый класс. Вы пробудили во мне ностальгические воспоминания, спасибо!
пфффф, и 2h+* <= B тоже