Олимпиадная информатика - 2015

Задача « Муравей на кубе»

Муравей Яша гуляет по поверхности куба с ребром длины а. По сигналу тревоги он бежит к входу в муравейник, который находится в одной из вершин куба. Из всех возможных путей муравей всегда выбирает самый короткий, и поэтому ему нужно заранее узнать длину кратчайшего пути до муравейника.

Формат входного файла cube.in Входной файл В первой строке записано единственное целое число а - длина ребра куба (1 < а < 1000000000). Вто- рая строка содержит три разделенных пробелами целых числа x, y и z - координаты муравья (0 < x,y, z <а). Гарантируется, что числа x, y и z определяют точку на поверхности куба с ребром а. Начало системы координат совпадает с входом в муравейник, оси координат направлены вдоль рёбер куба.

Формат выходного файла cube.out Выходной файл Выведите длину кратчайшего пути муравья. Ответ считается правильным, если абсолютная или относительная погрешность не превышает 10000.

var n,x,y,z,p:int64;
begin
assign(input, 'cube.in'); 
reset(input);
assign(output, 'cube.out');
 rewrite(output);
read(n,x,y,z);
if x=0 then p:=y*y+z*z else
if y=0 then p:=x*x+z*z else
if z=0 then p:=x*x+y*y else
if x=n then i f(y+n)*(y+n)+z*z < (z+n)*(z+n)+y*y then p:=(y+n)*(y+n)+z*z else p:=(z+n)*(z+n)+y*y else
if y=n then if (x+n)*(x+n)+z*z < (z+n)*(z+n)+x*x then p:=(x+n)*(x+n)+z*z else p:=(z+n)*(z+n)+x*x else
if (x+n)*(x+n)+y*y < (y+n)*(y+n)+x*x then p:=(x+n)*(x+n)+y*y else p:=(y+n)*(y+n)+x*x ;
write(sqrt(p):0:6);
close(input);
close(output);
end.

close
 

Разбор задачи №1 "Муравей на кубе"

Если муравей находится в одной грани куба со входом в муравейник, то при движении по кратчайшему пути он не пересекает ни одно из рёбер куба.

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

Она легко находится по теореме Пифагора. Если же муравей находится на какой-то другой грани, то одна из координат равна длине ребра куба.

При этом ему придется преодолеть одно из ребер куба. На пример, если муравей находится на верхней грани, то ему надо пересечь одно из двух верхних рёбер: фронтальное или левое. (см. рисунок в условии задачи).

Воспользовавшись развёрткой куба, легко понять что эти два пути снова вычисляются по тереме Пифагора: один катет равен сумме длины ребра и одной из меньших координат, а другой - второй меньшей координате. (для верхней грани это z+y и x при пути, пересекающем фронтальное ребро, и z+x и y для маршрута через левое верхнее ребро куба). Вычислим эти два расстояния и выберем меньший из них.