Cod sursa(job #72569)

Utilizator floringh06Florin Ghesu floringh06 Data 14 iulie 2007 12:54:17
Problema Regiuni Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.65 kb
{$IFDEF NORMAL}
  {$I-,Q-,R-,S-}
{$ENDIF NORMAL}
{$IFDEF DEBUG}
  {$I+,Q+,R+,S-}
{$ENDIF DEBUG}
{$IFDEF RELEASE}
  {$I-,Q-,R-,S-}
{$ENDIF RELEASE}

const MAX_N=1005;
      MAX_L=35;
      CST=30;

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

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

function compare(a,b: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])<>2) then sol:=sol+1;

writeln(fo,sol);
close(fo);

end.