Как узнать, что из двух прямоугольников {A;B} и {a;b} один можно вложить в другой (так, чтобы любая точка одного лежала внутри другого)?

GD Star Rating
loading...

28 Responses to Как узнать, что из двух прямоугольников один можно вложить в другой?

  1. Tuans:

    неужели проверкой неравенств координат?

  2. Taova:

    Уточню условие.

    1. Прямоугольники заданы шириной и высотой.
    2. Положение на плоскости любое.

  3. Ll5:

    ну дык показатели одного (w; h) меньше или равны показателям другого.

  4. Taova:

    если бы всё было так просто. Еще раз, положение на плоскости любое.

  5. Ll5:

    ну и что? да хоть где угодно в пространстве. Если заданы только ширина и высота, то фиолетово. Подходят пор размерам, значит можно вложить. Что не так то? Либо условие неполное.

  6. Taova:

    тогда что значит «подходят пор размерам»?

  7. Ll5:

    (a <= A && b <= B) || (a <= B && b <= A)

  8. Taova:

    это неверно, подумайте еще.

  9. LeCrazy:

    Чего–то ты явно не договариваешь.

  10. Taova:

    всё сказал, или что–то непонятно?

  11. LeCrazy:

    и какие преобразования допустимы для вложения?

  12. LeCrazy:

    что ты называешь шириной и высотой?

  13. Taova:

    A=|AB|, B=|BC| (красненьким мои обозначения у ABCD).

  14. Taova:

    любое положение на плоскости значит
    1. параллельный перенос;
    2. поворот.

  15. LeCrazy:

    ну, sign(a–A) == sign(b–B) || sign(a–B) == sign(b–A)

  16. LeCrazy:

    не, фигню написал.

  17. LeCrazy:

    (a–A)(b–B) >=0 | (a–B)(b–A) >= 0.

  18. Taova:

    я понял, почти тоже самое. Это слишком «строгое» условие. Неверно. Почитайте комментарии ниже: возможно, они подскажут решение.

  19. LeCrazy:

    а, понял–понял :

  20. LeCrazy:

    да, это тоже мимо.

  21. Taova:

    разве это не было написано выше?

  22. Re001:

    фактически, я так понимаю, что возможны два варианта —
    а) можно расположить параллельно
    б) можно вдоль диагонали
    Я думаю что это даже можно доказать через какие–н–дь минимумы. Сейчас попробую:

    Ось координат сейчас расположим по внешнему прямоугольнику ( который для проверки) {A,B}
    если взять угол alha пока произвольный, то
    нам необходимо условие, чтобы две проекции были меньше A и B
    a sin( alpha)+b cos(alpha) <= B,
    a cos( alpha) + b sin( alpha) <=A

  23. LeCrazy:

    не совсем, но по–любому неверно.

  24. Voem:

    Пусть внешний прямоугольник имеет стороны A и B, внутренний — a и b
    У нас три варианта развития событий:
    1. (a–A)(b–B) >=0 | (a–B)(b–A) >= 0 — можно
    2. Диагональ «внутреннего» прямоугольника больше диагонали «внешнего» — тогда точно нельзя
    3. ни одно из первых двух условий не выполнено. Тогда, возможно, «внутренний» прямоугольник можно вставить во «внешний», предварительно повернув. Не нарушая общности, будем считать, что B>=A и b>=a. Так как первое условие не выполнено, то «внутренний» прямоугольник можно расположить так, чтобы две его вершины лежали на сторонах «внешнего», см. картинку.

    размер 444x307, 6.55 kb

  25. Voem:

    Теперь немного выкладок.
    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+*

  26. Voem:

    то есть,

    *=sqrt(c^2–A^2)
    и
    m^2=a^2+k^2 равно (a^2/*^2)*(*^2+l^2) равно (a^2/*^2)*(*^2+(A–m)^2), парсер лох

  27. Re3:

    Я решал эту задачу девять лет назад на вступительных экзаменах в десятый класс. Вы пробудили во мне ностальгические воспоминания, спасибо!

  28. Voem:

    пфффф, и 2h+* <= B тоже

Добавить комментарий