Описание
На поверхности прямоугольного параллелепипеда {(x,y,z) | 0≤x≤L, 0≤y≤W, 0≤z≤H} отмечены две точки с координатами (x1,y1,z1) и (x2,y2,z2). Существует много путей, проходящих по поверхности параллелепипеда и соединяющих заданные точки

Задание
Требуется найти квадрат длины кратчайшего из таких путей


Входные данные
Файл входных данных содержит (в указанном порядке) следующие 9 целых чисел: L,W,H,x1,y1,z1,x2,y2,z2. Числа разделяются пробелами и/или символами перевода строки. Каждое из чисел L, W, H не превышает 100

Выходные данные
Вывести в выходной файл одно целое число - квадрат длины искомого пути


Например:

WAY.IN
3 4 4
1 2 4
3 2 1

WAY.OUT
25




Идеи
Развертка

Комментарии
 Пометим конечную точку краской. Пока краска не высохла, поставим параллелепипед начальной точкой на начало координат плоскости Oxy. Теперь будем перекатывать параллелепипед через его ребра всеми возможными способами, выполняя не более 5 перекатываний от начального положения. В результате конечная точка будет оставлять на плоскости Oxy отпечатки (считаем, что на параллелепипеде отпечатков не остается)

Так как способов перекатывания много, то и следов конечной точки тоже будет несколько. Минимальное из расстояний от начала координат плоскости Oxy до отпечатка конечной точки и будет ответом задачи.


Упражнения

  1. Докажите корректность приведенного алгоритма

  2. Можно ли уменьшить указанное в алгоритме число перекатываний? На сколько?


Решение

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}

program way;
var
 l,w,h,xx1,yy1,xx2,yy2,zz1,zz2:longint;
 res:longint;
 a:array[-6..6,-6..6] of boolean;

procedure readdata;
begin
 assign(input,'way.in');
 reset(input);
 read(l,w,h);
 read(xx1,yy1,zz1);
 read(xx2,yy2,zz2);
end;

procedure outdata;
begin
 assign(output,'way.out');
 rewrite(output);
 writeln(res);
 close(output);
end;

procedure init;
var
 i,j:integer;
begin
 for i:=-6 to 6 do
  for j:=-6 to 6 do
   a[i,j]:=false;
end;

procedure krut(i,j,x0,y0,l,w,h,x,y,z:longint;ll:integer);
begin
 if ll>4 then
  exit;
 if (abs(i)>4) or (abs(j)>4)then
  exit
   else
  a[i,j]:=true;
 if z=0 then
  begin
   if res>(xx1-(x0+x))*(xx1-(x0+x))+(yy1-(y0+y))*(yy1-(y0+y)) then
    res:=(xx1-(x0+x))*(xx1-(x0+x))+(yy1-(y0+y))*(yy1-(y0+y));
   exit;
  end;
 if (abs(i)<5) or (abs(j)<5) then
  begin
   krut(i+1,j, x0+l,y0, h,w,l, z,y,l-x,ll+1);
   krut(i-1,j, x0-h,y0, h,w,l, h-z,y,x,ll+1);
   krut(i,j+1, x0,y0+w, l,h,w, x,z,w-y,ll+1);
   krut(i,j-1, x0,y0-h, l,h,w, x,h-z,y,ll+1);
  end;
end;

procedure krut1(i,j,x0,y0,l,w,h,x1,y1,z1,x2,y2,z2:longint);
begin
 if (abs(i)>4) or (abs(j)>4) or (a[i,j]) then
  exit
   else
  a[i,j]:=true;
 if z1=0 then
  begin
   init;
   xx1:=x1;
   yy1:=y1;
   krut(0,0,0,0,l,w,h,x2,y2,z2,0);
   outdata;
   halt;
  end;
 if (abs(i)<5) or (abs(j)<5) then
  begin
   krut1(i+1,j, x0+l,y0, h,w,l, z1,y1,l-x1,z2,y2,l-x2);
   krut1(i-1,j, x0-l,y0, h,w,l, h-z1,y1,x1,h-z2,y2,x2);
   krut1(i,j+1, x0,y0+w, l,h,w, x1,z1,w-y1,x2,z2,w-y2);
   krut1(i,j-1, x0,y0-w, l,h,w, x1,h-z1,y1,x2,h-z2,y2);
  end;
end;
 
procedure makeall;
begin
 res:=maxlongint;
 krut1(0,0,0,0,l,w,h,xx1,yy1,zz1,xx2,yy2,zz2);
end;

begin
 init;
 readdata;
 makeall;
end.

 

© Особенности национальных задач по информатике