Как узнать, что из двух прямоугольников {A;B} и {a;b} один можно вложить в другой (так, чтобы любая точка одного лежала внутри другого)?
GD Star Rating
loading...
loading...
28 Responses to Как узнать, что из двух прямоугольников один можно вложить в другой?
Добавить комментарий Отменить ответ
Обсуждения в блоге
- ДОБРО ПОЖАЛОВАТЬ В НАУКУ!
- блогерс, кто может дать радиометр погонять на денёк?
- про IR лазеры теперь, чтоб те долго жили.
- Не уверен, что чисто алгебраические задачи будут тут уместны, но всё же.
- Швейцарские и грузинские археологи обнаружили в ходе раскопок человеческий череп, который доказывает, что уже 1,8 миллиона лет назад все люди, живущие на земле, принадлежали к одному и тому же виду приматов —
- Суббота.
- Господа, у меня своеобразный вопрос.
- Пару недель назад мы с каналом «Наука 2.
- Друзья, объясните мне пожалуйста, чем отличается альфа частица 3.
- Байты и биты.
неужели проверкой неравенств координат?
Уточню условие.
1. Прямоугольники заданы шириной и высотой.
2. Положение на плоскости любое.
ну дык показатели одного (w; h) меньше или равны показателям другого.
если бы всё было так просто. Еще раз, положение на плоскости любое.
ну и что? да хоть где угодно в пространстве. Если заданы только ширина и высота, то фиолетово. Подходят пор размерам, значит можно вложить. Что не так то? Либо условие неполное.
тогда что значит «подходят пор размерам»?
(a <= A && b <= B) || (a <= B && b <= A)
это неверно, подумайте еще.
Чего–то ты явно не договариваешь.
всё сказал, или что–то непонятно?
и какие преобразования допустимы для вложения?
что ты называешь шириной и высотой?
A=|AB|, B=|BC| (красненьким мои обозначения у ABCD).
любое положение на плоскости значит
1. параллельный перенос;
2. поворот.
ну, sign(a–A) == sign(b–B) || sign(a–B) == sign(b–A)
не, фигню написал.
(a–A)(b–B) >=0 | (a–B)(b–A) >= 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^2–A^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+(A–m)^2).
Домножаем на *^2, раскрываем скобки справа, переносим всё влево, имеем:
(*^2–A^2)*m^2+2*A*a^2*m–a^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 тоже