Cod sursa(job #45807)

Utilizator gurneySachelarie Bogdan gurney Data 1 aprilie 2007 22:32:36
Problema Regiuni Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.99 kb
program regiuni;
const
  nmax=2000;
  fin='regiuni.in';
  fout='regiuni.out';
type
  list1=^elem1;
  list=^elem;
  elem=record
    urm:list;
    x:integer;
    end;
  elem1=record
    urm:list1;
    fiu:list;
    end;
var
  old,nou:list1;
  st,dr:boolean;
  r,l,tmp:list1;
  x:array[1..nmax] of real;
  y:array[1..nmax] of real;
  a,b,c:array[1..nmax] of real;
  n,m,i,j,k,aux,d:longint;
  cap,ult,ult2:list1;
  n_new,n_old:longint;
  p,q,z:list;

function plus(x,y:real;d:integer):boolean;
  begin
    plus:=a[d]*x+b[d]*y+c[d]>=0;
  end;

begin
  assign(input,fin);
    reset(input);
    readln(n,m);
    for i:=1 to n do
      readln(a[i],b[i],c[i]);
    for i:=1 to m do
      readln(x[i],y[i]);
  assign(output,fout);
    rewrite(output);
    n_new:=1;
    new(nou);
    nou^.urm:=nil;
    nou^.fiu:=nil;
    new(ult);
    ult^.urm:=nil;
    nou^.urm:=ult;
    for i:=1 to m do
      begin
        new(p);
        p^.x:=i;
        p^.urm:=ult^.fiu;
        ult^.fiu:=p;
      end;
    for i:=1 to n do
      begin
        tmp:=nou^.urm;
        n_new:=0;
        new(old);
        old^.urm:=nil;
        old^.fiu:=nil;
        ult:=old;
        while tmp<>nil do
          begin
            st:=false;dr:=false;
            p:=tmp^.fiu;
            while p<>nil do
              begin
                if plus(x[p^.x],y[p^.x],i) then
                  begin
                    if st then
                      begin
                        new(z);
                        z^.urm:=l^.fiu;
                        l^.fiu:=z;
                        z^.x:=p^.x;
                      end
                    else
                      begin
                        st:=true;
                        new(l);
                        l^.urm:=ult^.urm;
                        ult^.urm:=l;
                        ult:=l;
                        new(z);
                        ult^.fiu:=z;
                        z^.urm:=nil;
                        z^.x:=p^.x;
                        inc(n_new);
                      end;
                  end
                else
                  begin
                    if dr then
                      begin
                        new(z);
                        z^.urm:=r^.fiu;
                        r^.fiu:=z;
                        z^.x:=p^.x;
                      end
                    else
                      begin
                        dr:=true;
                        new(r);
                        r^.urm:=ult^.urm;
                        ult^.urm:=r;
                        ult:=r;
                        new(z);
                        ult^.fiu:=z;
                        z^.urm:=nil;
                        z^.x:=p^.x;
                        inc(n_new);
                      end;
                  end;
                p:=p^.urm;
              end;
            tmp:=tmp^.urm;
          end;
        nou:=old;
      end;
    writeln(n_new);
  close(output);
end.