e-olymp 13. Паук и муха

Задача

В пустой прямоугольной комнате размерами [latex]A \times B \times C[/latex] (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится?

Входные данные

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке — координаты мухи [latex]X_1[/latex], [latex]Y_1[/latex] и паука [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex].

Все входные данные — целые числа, не превышающие 500.

Выходные данные

Единственное число — расстояние, на которое переместится паук, вычисленное с точностью до 2-х знаков после запятой.

Тесты

Входные данные Выходные данные
$3$ $4$ $8$

$0$ $0$ $3$ $4$ $0$

$5.00$
$2$ $2$ $8$

$1$ $1$ $2$ $1$ $4$

$5.00$
$6$ $4$ $3$

$5$ $1$ $0$ $2$ $1$

$6.08$
$30$ $60$ $27$

$13$ $21$ $8$ $0$ $17$

$38.33$
$40$ $40$ $40$

$10$ $5$ $8$ $40$ $37$

$72.03$

Код программы

Решение задачи

Суть решения задачи заключается в переходе от трехмерного пространства комнаты к двумерному с помощью «развёртки» комнаты на координатную плоскость.

Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции [latex]distance[/latex].
В простейшем случае, если паук находится на полу комнаты, т.е. его координата [latex]Z_2[/latex] нулевая, координаты паука [latex]X_2[/latex] и [latex]Y_2[/latex] в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции [latex]distance[/latex].
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.

Ссылки

Условие задачи на сайте E-Olymp
Код решения задачи

e-olymp 7612. Алекс и квадраты оригами

Задача

Алекс любит оригами — японское искусство складывания из бумаги. Большинство конструкций оригами начинаются с квадратного листа бумаги. Алекс собирается сделать подарок для своей матери. Подарочная конструкция требует три одинаковых квадратных листа бумаги, но у Алекса имеется только один прямоугольный лист. Он может из него вырезать квадраты, стороны которых должны быть параллельны сторонам листа. Помогите Алексу определить максимально возможный размер квадратов, который он способен вырезать.

Входные данные

В одной строке два целых числа [latex]h[/latex] и [latex]w[/latex] ([latex]1 ≤ h, w ≤ 1000[/latex]) — высота и ширина куска бумаги.

Выходные данные

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером [latex]h × w[/latex] так, чтобы их стороны были параллельны сторонам листа.

Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные Выходные данные
$100$ $100$ $50.000$
$10$ $80$ $10.000$
$50$ $76$ $25.333$
$60$ $27$ $20.000$
$8$ $3$ $2.667$

Код программы

Решение задачи

Существует два варианта оптимального расположения трех квадратов — три в один ряд,

или же два, соприкасающихся одной стороной, и третий над ними

Обозначим за [latex]a[/latex] меньшую сторону листа бумаги, а за [latex]b[/latex] — большую. Если [latex]a[/latex] не больше [latex]\frac{b}{3}[/latex], то оптимальным расположением квадратов в прямоугольнике будет первый вариант, а наибольшей возможной стороной квадратов является меньшая сторона листа бумаги [latex]a[/latex]. В противном случае рассмотрим два варианта:

  1. Если [latex]\frac{a}{2}<\frac{b}{3}[/latex], то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число [latex]\frac{a}{2}[/latex].
  2. Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число [latex]\frac{b}{3}[/latex].

Таким образом, в случае [latex]a>\frac{b}{3}[/latex] ответом будет служить большее из двух чисел [latex]\frac{a}{2}[/latex] и [latex]\frac{b}{3}[/latex].
Минимальное из [latex]\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex] и [latex]a[/latex] число и будет ответом.
Проверим нашу формулу:если [latex]a<\frac{b}{3}[/latex], то [latex] \max\left(\frac{b}{3},\frac{a}{2}\right)=\frac{b}{3} [/latex], и тогда [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=a[/latex]. Иначе [latex]\min\left(a,\max\left(\frac{b}{3},\frac{a}{2}\right)\right)=\max\left(\frac{b}{3},\frac{a}{2}\right)[/latex], что нам и требуется.

Ссылки

Условие задачи на сайте E-Olymp
Код решения задачи