Cod sursa(job #37472)

Utilizator gurneySachelarie Bogdan gurney Data 25 martie 2007 10:15:29
Problema Regiuni Scor 0
Compilator fpc Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 3.17 kb
program regiuni;
const
  nmax=2000;
  fin='regiuni.in';
  fout='regiuni.out';
type
  list=^elem;
  elem=record
    next:list;x:integer;
    end;

var
  h:array[1..nmax*2+1] of list;
  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:list;
  count: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]);
    new(cap);
    new(ult);
    cap^.next:=ult;ult^.next:=nil;
    ult^.x:=1;
    new(h[1]);
    h[1]^.next:=nil;
    for i:=1 to m do
      begin
        new(q);
        q^.x:=i;
        q^.next:=h[1]^.next;
        h[1]^.next:=q;
      end;
    for d:=1 to n do
      begin
        p:=cap^.next;
        ult2:=ult;
        while p<>ult^.next do
          begin
            q:=h[p^.x]^.next;
            while q<>nil do
              begin
                if plus(x[q^.x],y[q^.x],d) then
                  begin
                    k:=p^.x shl 1;
                    if h[k]=nil then
                      begin
                        new(h[k]);
                        h[k]^.next:=nil;
                        new(z);
                        z^.x:=k;
                        ult2^.next:=z;
                        z^.next:=nil;
                        ult2:=z;
                        new(z);
                        h[k]^.next:=z;
                        z^.next:=nil;
                        z^.x:=q^.x;
                      end
                    else
                      begin
                        new(z);
                        z^.x:=q^.x;
                        z^.next:=h[k]^.next;
                        h[k]^.next:=z;
                      end;
                  end
                else
                  begin
                    k:=p^.x shl 1 or 1;
                    if h[k]=nil then
                      begin
                        new(h[k]);
                        h[k]^.next:=nil;
                        new(z);
                        z^.x:=k;
                        ult2^.next:=z;
                        z^.next:=nil;
                        ult2:=z;
                        new(z);
                        h[k]^.next:=z;
                        z^.next:=nil;
                        z^.x:=q^.x;
                      end
                    else
                      begin
                        new(z);
                        z^.x:=q^.x;
                        z^.next:=h[k]^.next;
                        h[k]^.next:=z;
                      end;
                  end;
                z:=q;
                q:=q^.next;
                dispose(z);
              end;
            p:=p^.next;
          end;
        cap:=ult;
        ult:=ult2;
      end;
  close(input);
  assign(output,fout);
    rewrite(output);
    count:=0;
    z:=cap^.next;
    while z<>nil do
      begin
        inc(count);
        z:=z^.next;
      end;
    writeln(count);
  close(output);
end.