Cod sursa(job #466234)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 26 iunie 2010 12:24:04
Problema Fibo3 Scor 0
Compilator fpc Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 2 Marime 3.44 kb
program p1;
var f,g:text;
    a:array[0..100] of int64;
    n,nn,i,nr:longint;
    x1,x2,y1,y2:int64;

procedure preprop;
begin
    a[0]:=1;a[1]:=1;nn:=1;
    while a[nn]<=2000000000000000 do
    begin
         nn:=nn+1;
         a[nn]:=a[nn-1]+a[nn-2];
    end;
end;

procedure schimba(var x,y:int64);
var aux:int64;
begin
     aux:=x;
     x:=y;
     y:=aux;
end;

function cauta1(x:int64):longint;
var st,dr,ok,j,mij:longint;
begin
     st:=1;dr:=nn;ok:=0;j:=1;
     while (st<=dr)and(ok=0) do
     begin
          mij:=(st+dr) div 2;
          if a[mij]=x then ok:=mij
          else if a[mij]<x then st:=mij+1
          else begin dr:=mij-1;j:=mij;end;
     end;
     if ok>0 then j:=ok;
     cauta1:=j;
end;

function cauta2(x:int64):longint;
var st,dr,ok,j,mij:longint;
begin
     st:=1;dr:=nn;ok:=0;j:=nn;
     while (st<=dr)and(ok=0) do
     begin
          mij:=(st+dr) div 2;
          if a[mij]=x then ok:=mij
          else if a[mij]<x then begin st:=mij+1;j:=mij;end
          else begin dr:=mij-1;end;
     end;
     if ok>0 then j:=ok;
     cauta2:=j;
end;

procedure rezolva_dreapta(x1,y1,x2,y2:int64);
var  s1,s2:int64;
     c1,c2:longint;
begin
     if x1=x2 then
     begin
        if y1>y2 then schimba(y1,y2);
        s1:=y1+x1;
        s2:=y2+x2;
        c1:=cauta1(s1);
        c2:=cauta2(s2);
        nr:=nr+c2-c1+1;
     end
     else
        begin
             if x1>x2 then schimba(x1,x2);
             s1:=y1+x1;
             s2:=y2+x2;
             c1:=cauta1(s1);
             c2:=cauta2(s2);
             nr:=nr+c2-c1+1;
        end;
end;

function cauta(x:int64):boolean;
var st,dr,mij:longint;
    ok:boolean;
begin
     st:=1;dr:=nn;ok:=false;
     while (st<=dr) and (not ok) do
     begin
          mij:=(st+dr) div 2;
          if a[mij]=x then ok:=true
          else if a[mij]<x then st:=mij+1
                else dr:=mij-1;
     end;
     cauta:=ok;
end;

function pot(x1,y1,x2,y2:int64):boolean;
begin
     if (x2-x1>0)and(y2-y1>0) then pot:=true
     else
     begin
         if (x1-x2=0)or(y1-y2=0) then rezolva_dreapta(x1,y1,x2,y2);
         pot:=false;
     end;
end;

procedure rezolva_dreptunghi(x1,y1,x2,y2:int64);
var x11,x22,y22,y11,x3,x4,y3,y4,s1,s2:int64;
    c1,c2,mm:longint;
begin
    {punctul 1}
    if y1<y2 then y11:=y1
        else y11:=y2;
    if x1<x2 then x11:=x1
        else x11:=x2;
    {punctul 2}
    y22:=y11;
    if x1>x2 then x22:=x1
        else x22:=x2;
    {punctul 3}
    x3:=x22;
    if y1>y2 then y3:=y1
        else y3:=y2;
    {punctul 4}
    x4:=x11;
    y4:=y3;
    while pot(x11,y11,x3,y3) do
    begin
    mm:=nr;
    rezolva_dreapta(x11,y11,x22,y22);
    rezolva_dreapta(x11,y11,x4,y4);
    rezolva_dreapta(x3,y3,x22,y22);
    rezolva_dreapta(x3,y3,x4,y4);

    if cauta(x3+y3) then nr:=nr-1;
    if cauta(x11+y11) then nr:=nr-1;
    if cauta(x22+y22) then nr:=nr-1;
    if cauta(x4+y4) then nr:=nr-1;

    y11:=y11+1;x11:=x11+1;
    y22:=y22+1;x22:=x22-1;
    y3:=y3-1;x3:=x3-1;
    y4:=y4-1;x4:=x4+1;
    end;

end;

begin
    assign(f,'fibo3.in');reset(f);
    assign(g,'fibo3.out');rewrite(g);
    preprop;
    read(f,n);
    for i:=1 to n do
    begin
        read(f,x1,y1,x2,y2);
        nr:=0;
        if (x1=x2)or(y1=y2) then rezolva_dreapta(x1,y1,x2,y2)
        else rezolva_dreptunghi(x1,y1,x2,y2);

        writeln(g,nr);
    end;
    close(f);
    close(g);
end.