Cod sursa(job #37987)

Utilizator andrei_infoMirestean Andrei andrei_info Data 25 martie 2007 13:13:08
Problema Regiuni Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.43 kb
const nmax= 1000;
      hh = 666013;
type dr = record
        a,b,c:longint;
        end;
     pc = record
        x,y:longint;
        end;
     pnod = ^tnod;
     tnod = record
                val:longint;
                poz:integer;
                next:pnod;
                end;
var lpc:array[1..nmax] of pc;
    ldr:array[1..nmax] of dr;
    rdr,rpc:array[1..nmax] of longint;
    viz: array[1..nmax] of boolean;
    hash:array[0..hh] of pnod;
    a:array[1..nmax,1..nmax] of boolean; //false sub, true peste
    n,m:integer;

procedure citire;
var i:integer;
begin
assign(input,'regiuni.in'); reset(input);
readln(n,m);
for i:=1 to n do
        readln(ldr[i].a, ldr[i].b, ldr[i].c);
for i:=1 to m do
        readln(lpc[i].x, lpc[i].y);
close(input);
end;

procedure addhash(val:longint; poz:integer);
var p :pnod;
    pozhash:longint;
begin
pozhash:=val mod hh;
new(p); p^.val:=val; p^.poz:=poz; p^.next:=hash[pozhash];
hash[pozhash]:=p;
end;

function ok (l1,l2:integer):boolean;
var i:integer;
begin
ok:=true;
for i:=1 to n do
        if a[l1,i] <> a[l2,i] then
                begin
                ok:=false;
                exit;
                end;
end;

procedure cautahash(pc: integer);
var pozhash:longint;
    p:pnod;
begin
pozhash:=rpc[pc] mod hh;
p:=hash[pozhash];
while p <> nil do
        begin
        if p^.val = rpc[pc] then
                //if ok(pc, p^.poz) then
                        begin
                        viz[p^.poz]:=true;
                        end;
        p:=p^.next;
        end;
end;

procedure calc;
var i,j:integer;
    aux:longint;
begin
randomize;
for i:=1 to n do
        rdr[i]:=random(2000000) + 1;
for i:=1 to m do
        begin
        for j:=1 to n do
                begin
                aux:=lpc[i].x * ldr[j].a  + lpc[i].y * ldr[j].b;
                if aux < -ldr[j].c then
                        a[i,j]:=false
                else  begin a[i,j]:=true; rpc[i]:=rpc[i]+rdr[j]; end;

                end;
        addhash(rpc[i],i);
        end;
end;

procedure afla;
var rez:longint;
    i,j:integer;
    k:boolean;
begin
rez:=0;
for i:=1 to m do
        if not viz[i] then
                begin
                inc(rez);
                cautahash(i);
                viz[i]:=true;
                end;
assign(output,'regiuni.out'); rewritE(output);
writeln(rez);
close(output);
end;

begin
citire;
calc;
afla;
end.