Интересная алгоритмическая задачка от Airbus

[Padawan]

A_I
Вариант с наибольшей площадью будет тоже скорее всего ограничен дугами окружностей. Мой вариант можно чуть увеличить, скруглив угол в точке $G$, а вот насколько -- считать надо. И нет никакой уверенности, что это будет фигура наибольшей площади.

[wrest]

Padawan в сообщении #1669697 писал(а):

Вот такую фигуру можно запихать: $BJHKLMFGIB$. Даже вырезал из бумаги и провращал внутри квадрата.

А точка B там точно не лишняя? Т.е. не $JHKLMFGIJ$?

[mihaild]

Padawan, я так понимаю, Ваш вариант - это открыть дверь наполовину и пропихнуть с поворотом что получится?
Напоминает задачу о перемещении дивана.
(её мы тут точно не решим)

[Padawan]

mihaild
Более того, во время поворота дверцу тоже будем вращать

-- Пн янв 13, 2025 00:15:50 --

wrest
Этот кусочек ($BJI$) не мешает, поэтому пусть будет.

-- Пн янв 13, 2025 01:03:14 --

Padawan в сообщении #1669702 писал(а):

Мой вариант можно чуть увеличить, скруглив угол в точке $G$

Можно добавить дугу окружности радиуса $1-\frac{\sqrt 2}2$ с центром в точке $E$.

[Geen]

А если дверь открывается, то может ли часть фигуры вываливаться наружу?

[Sender]

Мне кажется, оптимальная фигура должна быть асимметричной, что-то в духе жирной запятой. И внешний обвод имеет не постоянную кривизну, а уменьшающуюся к хвостику, чтобы по мере пропихивания и закрытия дверцы лучше заполнять центральную часть квадрата... Хм, наверное, для начала можно задаться вопросом, какую самую длинную кривую можно так пропихнуть.

[sergey zhukov]

Довольно очевидная оптимизация исходной фигуры (которая заметается закрывающейся дверцей) - это "поворот" одной ее половины вот так:

Теряется желтая площадь ($\frac{4-\pi}{16}$), но приобретается красная ($\pi\frac{3}{64}$).


Можно еще немного пожертвовать острыми кончиками (которые и так немного подрезаются в этом варианте, совсем чуть-чуть), чтобы увеличить степень поворота (в этом варианте угол красного сектора равен $67,5^\circ$). Это должно еще больше увеличить площадь.

[Padawan]

sergey zhukov
Сколько в итоге получается?

[sergey zhukov]

Padawan
$(+\frac{7\pi-16}{64})$ (для единичного квадрата) минус из этого чуть-чуть по кончикам.

[manul91]

Возможно, "протаскивать-и-поворачивать-вокруг-конца двери" фигуру нужно по чуть-чуть, по мере (и одновременно с) открыванием двери - это наверно даст еще лучший результат (чем просто поворот двери на полоборота, потом поворот фигуры, и наконец поворот двери до конца - как на картинке).
Правда "ограниченной дугами окружностей" такая фигура вряд ли будет....

[sergey zhukov]

manul91
Да, я тоже так думаю. Я хотел рассмотреть общий вариант, но сначала решил попробовать этот частный.
Более общий вариант - неперерывный поворот фигуры в процессе "пропихивания". Проблема в том, что неизвестна траектория центра вращения фигуры.

Есть два простых варианта: центр вращения движется по стенкам будки ( фигура катается по стенкам без проскальзывания) и центр вращения находится на конце двери (вот эта картинка выше - частный случай второго варианта). Эти ограничения позволяют построить две фигуры. Можно попробовать это сделать.

[manul91]

sergey zhukov в сообщении #1669739 писал(а):

Проблема в том, что неизвестна траектория центра вращения фигуры.

Как бы фигура вроде всегда должна поворачиваться вокруг конца двери (чтобы максимально утилизировать мгновенно-доступный зазор) - значит траектория "мгновенного центра вращения" совпадает с траекторию конца двери.

sergey zhukov в сообщении #1669739 писал(а):

Есть два простых варианта: центр вращения движется по стенкам будки ( фигура катается по стенкам без проскальзывания) и центр вращения находится на конце двери (вот эта картинка выше - частный случай второго варианта).

Первый "вариант" непонятно о чем. Разумеется фигура при "поворачивании" должна не выходить за стенок. "Без проскальзывания" - такого требования в условии вроде нет.

[sergey zhukov]

manul91
Почему она должна поворачиваться вокруг конца двери? "Без проскальзывания" по двери - такого же условия тоже нет. В мгновенном зазоре есть две граничные точки, можно поворачивать фигуру вокруг каждой из них при " пропихивании".
Без проскальзывания по стенкам - это просто чтобы траектория центра вращения была известна. Поиск под фонарем. Понятно, что условия этого не оговаривают.

[manul91]

sergey zhukov в сообщении #1669741 писал(а):

Почему она должна поворачиваться вокруг конца двери?

Интуитивно: ) чтобы максимально использовать мгновенно-доступный зазор. Центр вращения должен же быть где-нибудь, если фигура поворачивает не вокруг самой-внутренней точки зазора - меньше площади пролезет. Вроде.
Насчет "не проскальзывания" - я думаю проскальзывание по чему угодно не только допустимо но и желательно.

-- 13.01.2025, 11:32 --

sergey zhukov в сообщении #1669741 писал(а):

В мгновенном зазоре есть две граничные точки, можно поворачивать фигуру вокруг каждой из них при " пропихивании".

Какова будет "вторая граничная точка в мгновенном зазоре" при фиксированном раскрытии двери, конкретно?
Так по моему "зазор" - это с одной стороны точка - конец дверцы, с другой стороны - две противоположные стенки квадрата.
Как бы оно не было, поворот вокруг точки в которой фигура упирается в стенки исключает "проскальзывание" - но "проскальзывание" выглядит выигрышной стратегией, непонятно зачем его не использовать (вот в вашем примере на картинке проскальзывание есть как по конце двери так и по стенок). Имхо алгоритмически наверно чередовать открывание двери чуть-чуть еще (с проскальзыванием по контура фигуры), потом поворот фигуры вокруг конца двери (с проскальзыванием по стенкам), и потом повторить - както-так.
Да и чисто интуитивно по-бытовому, когда протискиваемся в таких условий, то поворот происходит вокруг внутренней части препятствия а "зад" скользит по стенках (проскальзывание - залог успеха). Лол : )))

[sergey zhukov]

Вот построение одного из вариантов решения, когда фигура вращается вокруг точки касания двери (без проскальзывания по двери). В данном случае скорость вращения выбрана постоянной, угол поворота равен углу открытия двери:


Получается фигура, ограниченная тремя окружностями диаметрами, равными 1 и 2. Если выбрать другую зависимость скорости вращения фигуры от угла поворота двери, то можно получить другие решения (не круглые) . Какая из них максимизирует площадь - это вопрос. Вероятно, нужно вращать тем быстрее, чем шире зазор между дверью и стенками.