Cod sursa(job #37675)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 25 martie 2007 11:51:42
Problema Regiuni Scor 90
Compilator fpc Status done
Runda preONI 2007, Runda 4, Clasele 11-12 Marime 2.12 kb

  const
       FIN = 'regiuni.in';
       FOUT = 'regiuni.out';
       NMAX = 1005;

  type
       sir = array[ 1..NMAX ] of longint;
       matrix = array[ 1..NMAX ] of sir;
       vect = array[ 1..NMAX ] of longint;

   var
       A, B, C, X, Y, IND : vect;
       AA : array[ boolean ] of sir;
       P : matrix;
       cnt : array[ 0..3] of longint;
       N, M, k, ans : longint;
       f, g : text;

  procedure read_data;
   var i : longint;
   begin
    assign( f, FIN ); reset( f ); readln( f, N, M );
    for i := 1 to N do readln( f, A[i], B[i], C[i] );
    for i := 1 to M do readln( f, X[i], Y[i] );
    close( f );
   end;

  procedure build_P;
   var i, j : longint;
   begin
    for i := 1 to M do
     begin
      ind[i] := i;
      for j := 1 to N do
        if A[j] * X[i] + B[j] * Y[i] + C[j] > 0 then P[ i, j ] := 1
                                                else P[ i, j ] := 2;
     end;

   end;

   procedure radix;
    var i, j : longint;
        l : boolean;
    begin

     l := false;
     for i := 1 to M do AA[ false, i ] := i;

     for i := N downto 1 do
       begin
         fillchar( cnt, sizeof( cnt ), 0 );
         for j := 1 to M do
               inc( cnt[ P[ AA[ l, j ] , i ] ] );
         for j := 1 to M do
            begin
              AA[ not l, CNT[ P[AA[l,j],i] - 1] + 1 ]  := AA[ l, j ];
              inc( CNT[ P[ AA[l,j],i] - 1 ] );
            end;
         l := not l;
     end;

   for i := 1 to M do ind[i] := AA[ l, i ];
  end;

  function compara( var A, B : sir ) : integer;
   var i : longint;
    begin
      for i := 1 to N do
       if A[i] <> B[i] then begin compara := 1; exit; end;
       compara := 3;
    end;



    procedure solve;
     var i : longint;
      begin
        build_P;
        radix;
        ans := 1;
        for i := 2 to M do
          if compara( P[ind[i]], P[ind[i-1]] ) <> 3 then inc( ans );
      end;

   procedure save;
    begin
     assign( g, FOUT ); rewrite( g ); writeln( g, ans ); close( g );
    end;

    begin
     read_data;
     solve;
     save;
    end.