Олимпиадная информатика — 2015
Разбор и решение задач муниципального уровня
Задача « Муравей на кубе»
Муравей Яша гуляет по поверхности куба с ребром длины а. По сигналу тревоги он бежит к входу в муравейник, который находится в одной из вершин куба. Из всех возможных путей муравей всегда выбирает самый короткий, и поэтому ему нужно заранее узнать длину кратчайшего пути до муравейника.
Разбор задачи №1 «Муравей на кубе»
Если муравей находится в одной грани куба со входом в муравейник, то при движении по кратчайшему пути он не пересекает ни одно из рёбер куба.
В этом случае одна из его координат равна нулю и траектория кратчайшего пути — гипотенуза прямоугольного треугольника (может быть вырожденного) с катетами, равными двум другим координатам.
Она легко находится по теореме Пифагора. Если же муравей находится на какой-то другой грани, то одна из координат равна длине ребра куба.
При этом ему придется преодолеть одно из ребер куба. На пример, если муравей находится на верхней грани, то ему надо пересечь одно из двух верхних рёбер: фронтальное или левое. (см. рисунок в условии задачи).
Воспользовавшись развёрткой куба, легко понять что эти два пути снова вычисляются по тереме Пифагора: один катет равен сумме длины ребра и одной из меньших координат, а другой — второй меньшей координате. (для верхней грани это z+y и x при пути, пересекающем фронтальное ребро, и z+x и y для маршрута через левое верхнее ребро куба). Вычислим эти два расстояния и выберем меньший из них.
Источник