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

[A_I]

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

(Оффтоп)

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

[Padawan]

Втиснуть и дверцу закрыть потом?

[A_I]

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

Втиснуть и дверцу закрыть потом?

Да.
Хотя у меня нет оригинала текста, а только перевод, как я его написал стартовом посте (комментарии в скобках мои).
Вообще для сложности и методов видимо не важно, закрывать дверь или нет.

[Padawan]

Если не закрывать, то, очевидно, всю будку можно заполнить квадратом, неинтересно.

А если закрывать, то интересно, можно ли запихать площадь больше, чем $a^2-\pi/4\cdot a^2$

[A_I]

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

Если не закрывать, то, очевидно, всю будку можно заполнить квадратом, неинтересно.

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

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

А если закрывать, то интересно, можно ли запихать площадь больше, чем $a^2-\pi/4\cdot a^2$

Я понял, что можно. Также интересно, надо ли в процессе "впихивания" ещё и открытием-закрытием дверцы управлять для достижения бОльшего результата?

[wrest]

То есть в единичный квадрат можно "протащить" фигуру площадью больше чем $1-\dfrac{\pi}{4}$? Так вот сразу и не верится...
Или не хватает какого-то условия, типа что дверь хоть и открывается внутрь, но не полностью?

[A_I]

wrest в сообщении #1669684 писал(а):

Или не хватает какого-то условия, типа что дверь хоть и открывается внутрь, но не полностью?

Условия все (те что в тексте перевода).
Насколько я понимаю, такого рода задачки призваны показать способность больше к логическому мышлению, поэтому не удивлюсь, что правильно засчитанным будет и ответ с приведенной формулой и ответ с численными методами, например, расчета фигуры "непростой" формы, протискиваемой через открытую наполовину дверь.

-- 12.01.2025, 21:40 --

Поинтересовался у коллеги, который более детально знает по сути задачи (он то о ней и рассказал).
Перевод полный.
Тут всё равно надо считать площадь сложной фигуры при "приоткрытой" дверце, чтобы потом сравнить с "формульной". Но там как раз больше интересовал алгоритм численных методов. Они смотрели, насколько претендент умеет сам оценивать условия в смысле возможных путей решения, разбивать задачу на подзадачи и т.д., ну и в конечном итоге должен представить четкий алгоритм, производящий вычисления с заданной точностью.

(Оффтоп)

Я тоже не знаю, но не удивлюсь, если в "приоткрытую" дверь можно впихнуть тело большей площади

[wrest]

A_I в сообщении #1669686 писал(а):

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

Ну это ж тоже на бумажке...
Для открытой наполовину (под 45 градусов) двери у меня получается (для единичного квадрата)
$S=\dfrac{5}{8} \pi \left(\dfrac{3-2\sqrt{2}}{2}\right)\approx 0,168$

[A_I]

wrest в сообщении #1669688 писал(а):

Для открытой наполовину (под 45 градусов) двери у меня получается (для единичного квадрата)
$S=\dfrac{5}{8} \pi \left(\dfrac{3-2\sqrt{2}}{2}\right)\approx 0,168$

Ну то есть, меньше, чем при открытой полностью, потом закрытой..
А форма тела какая?

[wrest]

A_I в сообщении #1669686 писал(а):

производящий вычисления с заданной точностью.

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

-- 12.01.2025, 21:00 --

A_I в сообщении #1669689 писал(а):

А форма тела какая?

Сектор круга. Т.е. $5/8$ площади круга радиусом $\dfrac{2-\sqrt{2}}{2}$

[A_I]

wrest в сообщении #1669691 писал(а):

Сектор круга.

Мне представляется что-то типа (коряво от руки, зато быстро, думаю, форму передаёт ):

Знак вопроса - можно ли ещё "довпихивать" в процессе закрытия дверцы?

[Утундрий]

Я так понял, что дверцу можно перемещать как угодно, лишь бы она не выходила из будки.

[A_I]

Утундрий в сообщении #1669693 писал(а):

Я так понял, что дверцу можно перемещать как угодно, лишь бы она не выходила из будки.

Да, это точное условие.

[Padawan]

Вот такую фигуру можно запихать: $BJHKLMFGIB$. Даже вырезал из бумаги и провращал внутри квадрата.
Площадь, если не ошибся в расчетах, $0.2834$. Это больше, чем $1-\pi/4=0.2146$.

[A_I]

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

Вот такую фигуру можно запихать: $BJHKLMFGIB$. Даже вырезал из бумаги и провращал внутри квадрата.
Площадь, если не ошибся в расчетах, $0.2834$. Это больше, чем $1-\pi/4=0.2146$.

То есть, уже доказано, что будет больше.
Но, кажется есть варианты и с ещё большей площадью, но уже не вычислимые аналитически?