Давайте рассмотрим ещё одну задачу на геометрию, аналоги которой довольно часто встречаются:
Если бы в задаче разрешалось класть открытку в конверт только параллельно его сторонам, тогда мы бы могли решить задачу с помощью простой проверки x <= X and y <= Y (предварительно повернув конверт и открытку так, чтобы длинная сторона была вдоль оси абсцисс).
Но в этой задаче всё интереснее, и нам предлагают найти угол, на который, возможно, необходимо повернуть открытку, чтобы она поместилась в конверт. Это можно делать разными способами, например с помощью бинарного поиска. Однако я предлагаю разобрать аналитическое решение.
Рассмотрим две ситуации:
- x <= X, тогда поворачивать открытку не стоит, потому что это увеличит её высоту;
- иначе, повернём так, чтобы её ширина была равна X.
Рассмотрим второй случай подробнее, а именно, составим уравнение для ширины, которая получается, если повернуть открытку на угол alpha:
В ходе вывода формулы получилось квадратное уравнение, оно не всегда имеет корни. Если дискриминант меньше нуля, значит мы никак не можем повернуть открытку, чтобы получилось равенство. А это значит, что либо открытка очень маленькая (и как её ни поворачивай, она свободно помещается по ширине), либо - большая (и как её ни поворачивай, она никак не поместится по ширине). В обоих этих случаях можно взять угол поворота равный 0.
Тогда решение задачи будет состоять лишь из записи формул и нескольких условий (нам ведь надо проверить, что хотя бы при одном из полученных углов поворота открытка помещается в конверт).
Стоит обратить внимание на сравнения в лямбда-функции, они все сделаны с учётом погрешности eps, потому что вычисления с вещественными числами всегда делаются с некоторыми округлениями, и надо это учитывать. Я принял eps равной 0.000001, вы можете поэкспериментировать с другими числами и написать в комментариях, что получилось.
Предыдущий выпуск: Задача 716. Треугольник Максима
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.