Cod sursa(job #37904)

Utilizator mipsPavel Mircea mips Data 25 martie 2007 13:03:12
Problema Regiuni Scor 50
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.74 kb
const max=1000;
type punct= record x,y:longint;end;
     ecuatie=record a,b,c:longint;end;
     hashing=array[0..max div 20] of longint;
var ec:array[0..max] of ecuatie;
    pct:array[0..max] of punct;
    i,j,n,m:longint;rez:ecuatie;
    parti:array[0..max,0..max] of byte;
    hash:array[0..max] of hashing;t:longint;
    function cmp(a,b:hashing):boolean;
    var i,j:longint;
    begin
    cmp:=false;
    for i:=1 to n div 20+1 do
    if (a[i]<b[i]) then cmp:=true
    else
    if (a[i]>b[i]) then break;
    end;
procedure Quicksort(l, r: longint);
var
  i, j: longint;
    v,help:hashing;
    begin
v := hash[(l+r) div 2];
i := l; j := r;
repeat
while cmp(hash[i], {<} v) do inc(i);
while cmp(v {<}, hash[j]) do dec(j);
if i <= j then begin
Help := hash[i]; hash[i] := hash[j]; hash[j] := Help;
inc(i); dec(j);
end;
until i > j;
if l < j then Quicksort(l, j);
if i < r then Quicksort(i, r);
end;
procedure buildec(p1,p2:punct);
begin
rez.a:=p1.y-p2.y;
rez.b:=p2.x-p1.x;
rez.c:=p1.x*p2.y-p1.y*p2.x;
end;
function valhash(pct,index:longint):longint;
var p,k,i:longint;
begin
p:=0;k:=1;
for i:=index*20 downto (index-1)*20 do
begin
p:=p+k*parti[pct,i];
k:=k*2;
end;
valhash:=p;
end;
begin
assign(input,'regiuni.in');
reset(input);
readln(n,m);
for i:=1 to n do
readln(ec[i].a,ec[i].b,ec[i].c);
for i:=1 to m do
readln(pct[i].x,pct[i].y);
for i:=1 to m do
for j:=1 to n do
begin
if pct[i].x*ec[j].a+pct[i].y*ec[j].b+ec[j].c<0 then
parti[i,j]:=0
else
parti[i,j]:=1;
end;
for i:=1 to m do
for j:=1 to n div 20+1 do
hash[i,j]:=valhash(i,j);
quicksort(1,m);t:=0;
for i:=1 to m-1 do
if cmp(hash[i],hash[i+1]) then
inc(t);
assign(output,'regiuni.out');
rewrite(output);
writeln(t+1);
close(output);
end.