Cod sursa(job #65384)

Utilizator info_arrandrei gigea info_arr Data 9 iunie 2007 11:18:32
Problema Regiuni Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.5 kb
const MAX_N=1005;
      MAX_L=35;
      CST=30;

type vector=array[0..MAX_L] of integer;

var s:array[0..MAX_N,0..MAX_L] of integer;
    a,b,c:array[0..MAX_N] of integer;
    aux:array[0..MAX_L] of integer;
    sol,m,n,i,j,x,y,k:integer;
    fi,fo:text;

function compare(b,a:vector):integer;
var i,ok:integer;
begin
ok:=0;
for i:=0 to MAX_L do begin
 if (a[i]>b[i]) then begin compare:=1; ok:=1; break; end;
 if (a[i]<b[i]) then begin ok:=-1; break; end;
end;
if ok=0 then compare := 2;
if ok=-1 then compare := -1;
end;

begin
assign(fi,'regiuni.in'); reset(fi);
assign(fo,'regiuni.out'); rewrite(fo);
readln(fi,n,m);
fillchar(s,sizeof(s),0);
for i:=1 to n do
 readln(fi,a[i],b[i],c[i]);
for i:=1 to m do
 begin
  readln(fi,x,y);
  for j:=1 to n do
   if (a[j]*x+b[j]*y+c[j]>0) then
    s[i][j div CST]:=s[i][j div CST] or (1 shl (j mod CST));
 end;
for i:=1 to m do
 begin
  j:=i;
  while (j div 2<>0)and(compare(s[j],s[j div 2])=1) do
   begin
    aux:=s[j];
    s[j]:=s[j div 2];
    s[j div 2]:=aux;
    j:=j div 2;
   end;
 end;
i:=m;
while (i>1) do
 begin
  aux:=s[1];
  s[1]:=s[i];
  s[i]:=aux;
  dec(i);

  j:=1;
  while (1>0) do
   begin
    k:=2*j;
    if (k>i) then break;
    if (k+1<=i) and (compare(s[k+1],s[k])=1) then inc(k);
    if (compare(s[j],s[k])>=1) then break;

    aux:=s[j];
    s[j]:=s[k];
    s[k]:=aux;

    j:=k;
   end;
 end;
sol:=1;
for i:=2 to m do
 if (compare(s[i],s[i-1])=1) then inc(sol);
writeln(fo,sol);
close(fo);

end.