Удав, Задача на координаты и направление Опции

[1qsd]

Помогите решить вот эту несложную задачу. Преподаватель говорит, что решать её нужно как то через матрицы.

Удав расположен в виде нескольких линий, из которых каждая следущая перпендикулярна предыдущей. Направление каждой линии и её протяженность задаются буквами "L" , "R" и числом.

Например 25L15R5 ("25" - длина линии = 25, "L" - поворачивает на 90 градусов влево, "15" - длина линии = 15 , "R" - поворачивает на 90 градусов вправо , "5" - длина линии = 5).

Определить, пересечет ли он себя.

Сообщение отредактировано: 1qsd - 26.03.2007 15:17

[Lapp]

Коллеги, я не вполне все же вас понял..
Michael_Rybak, если одно звено полностью включает другое (этот случай ты называешь "касанием"?) то это значит, что подходящие к внутреннему (полностью включенному другим) дадут то, что я называю пересечением (наличие общих точек, включая концы). Поскольку в задаче спрашивается, самопересекается удав или нет - то этого будет достаточно, чтобы ответить "ДА". Вывод программой конкретных пересечений - это моя блажь, отладочная инфа.

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

Malice, твой первый тест (10L10L10R10R10R30) я прохожу нормально. А второй (ботинок с красным каблуком) я что-то не пойму.. Напиши его строчкой, плз.
Ааааа... понял. Приход обратно сзади... подкрасться тмхой сапой, и... O'kay, подумаю.

Остается одна проблема... Вот такая:
10L0L5
То есть звено нулевой длины и поворот назад. Такую ситуацию я не отлавливаю.. Но работаю над этим!

const
  m=100;

var
  x,y:array[0..m]of integer;
  Dir:record
    x,y:integer
  end;
  i,j,n,e,l,z:integer;
  c:char;
  s:string;
  f:file of char;

begin
  x[0]:=0; y[0]:=0;
  Dir.x:=1; Dir.y:=0;
  Assign(f,'boa.dat');
  Reset(f);
  n:=0;
  while not EoF(f) do begin
    Read(f,c);
    c:=UpCase©;
    if (c in ['L','R'])or EoF(f) then begin
      Inc(n);
      if EoF(f) then s:=s+c;
      Val(s,l,e);
      x[n]:=x[n-1]+Dir.x*l;
      y[n]:=y[n-1]+Dir.y*l;
      s:='';
      with Dir do case c of
        'L':begin z:=x; x:=-y; y:=z end;
        'R':begin z:=x; x:=y; y:=-z end;
      end
    end
    else s:=s+c
  end;

  for i:=4 to n do begin
    j:=i mod 2 +1;
    while j<i-2 do begin
      if Odd(i) and 
        ((x[i]-x[j])*(x[i-1]-x[j])<=0) and ((y[j]-y[i])*(y[j-1]-y[i])<=0)
        or not Odd(i) and 
        ((y[i]-y[j])*(y[i-1]-y[j])<=0) and ((x[j]-x[i])*(x[j-1]-x[i])<=0)
      then WriteLn('Bonds #',j,' and #',i,' are crossed over');
      Inc(j,2)
    end
  end
end.