Cod sursa(job #38200)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 25 martie 2007 15:47:13
Problema Regiuni Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.25 kb

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

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

   var
       A, B, C, X, Y, IND : vect;
       P : matrix;
       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;

  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 else
       if A[i] > B[i] then begin compara := 2; exit; end;
       compara := 3;
    end;

   procedure poz( lo, hi : longint );
    var i, j, di, dj, aux : longint;
     begin
      di := 0; dj := - 1; i := lo; j := hi;
      while i < j do
        begin
         if compara( P[ind[i]], P[ind[j]] ) = 2
                      then
                           begin
                             aux := di; di := - dj; dj := - aux;
                             aux := ind[i]; ind[i] := ind[j]; ind[j] := aux;
                            end;
        i := i + di;
        j := j + dj;
        end;
     k := i;
   end;

   procedure quick( lo, hi : longint );
    begin
     if lo < hi then
       begin
         poz( lo, hi );
         quick( lo, k - 1 );
         quick( k + 1, hi );
       end;
    end;

    procedure solve;
     var i : longint;
      begin
        build_P;
        quick( 1, M );
        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.