Влезет ли параллелепипед в четверть цилиндра?

Question

[rastr]

Добрый вечер, есть задача.
Дан цилиндр разделенный на 4 равные части(вертикально), считайте классическая дверь при входе в ТЦ, с заданным радиусом и высотой. А так же дан параллелепипед, с заданной шириной, длинной и высотой. Надо узнать, влезет ли параллелепипед в четверть цилиндра. При этом параллелепипед можно проносить, если он стоит на одной из граней.
В чем собственно загвоздка: я решил изначально предполагать, что параллелепипед (далее просто коробка) вмещается в четверть цилиндра. Коробка не должна вмещаться при следующих случаях:
1) Если хотя бы одна сторона больше чем max(radius, height)
2) Если три стороны больше, чем min(radius, height)
Но тем не менее остаются не пройдённые тесты к задаче. Какие случаи еще можно рассмотреть в добавок к моим?
Заранее спасибо :)

Comments

[Денис Загаевский]

Ты взял очень простые случаи. По диагонали можно воткнуть гораздо более длинный параллелепипед, чем max(radius, height), например.

[rastr]

Денис Загаевский, Я забыл уточнить в вопросе, что параллелепипед можно проносить только при условие, что он на одной из граней находится. Сейчас подправлю.

[Alexandroppolus]

rastr, в моём ответе в обоих кейсах коробка стоит одной гранью на полу.

Answer 1

[Alexandroppolus]

Коробка не должна вмещаться при следующих случаях:
1) Если хотя бы одна сторона больше чем max(radius, height)
2) Если три стороны больше, чем min(radius, height)

оба критерия - косячные.
1) Допустим, H = 1, R = 10. Тогда влезет коробка со сторонами a=1, b=0.1, c=12
2) H=10, R=10, не влезет кубик со сторонами 9.

тут не всё так просто )

Comments

[Alexandroppolus]

Собственно, условие, что коробка должна стоять на полу, всё упрощает.
Выбираем наибольшую сторону коробки, которая не превосходит высоту. Ставим коробку чтобы это ребро было вертикально. Задача превращается в двумерную, где вариантов только 2: либо упереть угол основания коробки в угол сектора и смотрим, что R^2 >= a^2 + b^2, либо размещаем основание под 45 гр. к сторонам сектора и смотрим, что другие два угла не вылезли - там надо убедиться, что R^2 >= a^2 / 2 + (a+b)^2 / 2, где a и b - стороны основания коробки, a <= b

[Alexandroppolus]

поправки

[Wataru]

Alexandroppolus, А почему именно 45 градусов?

[Alexandroppolus]

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

Answer 2

[Wataru]

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

Как проверить прямоугольник на впихивание в сектор? Если коробка помещается, ее можно в секторе вертеть и двигать, пока она не будет касаться границы сектора тремя вершинами. Получаются случаи: угол коробки совспадает с уголом сектора (диагональ прямоугольника <= радиуса), одна точка на прямой стороне сектора и две на круглой, 2 угла на двух прямых сторонах и одна на круглой.

Два последних случая надо порисовать, ввести какие-то переменные (например во втором случае можно ввести x и y - длины отрезков от угла сектора до углов прямоугольника) решить систему квадратных уравнений (длины сторон заданны, третья точка лежит на окружности) и проверить, что четвертая, свободная точка лежит внутри.

Что бы не плодить еще и случаи с порядком вершин советую перебрать 3! перестановок всех длин параллелипипида. Третья всегда будет высотой, дву другие в заданном порядке задают расположение точек. Например в первом случае первая длина - будет шириной прямоугольника, а вторая - высотой. В случае касания двумя точками двух прямых сторон, первая длина - будет стороной отсекающей угол, и т.д.

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

Comments

[Wataru]

На самом деле случаев меньше - можно забить на касание двумя углами окружности. В этом случае можно двигать коробку вдоль стороны. Так что остается только один нетривиальный случай - 2 угла на прямых сторонах и одна на окружности.

[Adamos]

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

P.S. Доказательствами заморачиваться не стал, хотя там нетрудно выводится формула по синусам, косинусам и Пифагору. Взял векторный редактор, нарисовал четверть круга и вписанный в нее прямоугольник. Повернул его - углы далеко вылезли за круг.

[Wataru]

Adamos, неверно. Очень тонкий прямоугольник можно положить вдоль хорды. Длина ее - sqrt(2)r. Но это отрезок. Однако достаточно тонкий прямоугольник может иметь длину достаточно близкую к этому - что явно больше радиуса.

[Adamos]

Wataru, да, действительно. На это у меня сейчас фантазии не хватило ;)