Cod sursa(job #41749)

Utilizator Bluedrop_demonPandia Gheorghe Bluedrop_demon Data 28 martie 2007 15:44:10
Problema Regiuni Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.23 kb
{
    Problema regiuni
}

Program regiuni;

Type dreapta = record
                a, b, c : Longint;
               end;
     elm = record
            x, y : Longint;
           end;
     vector = array[1..1000] of elm;
     ref = ^cik;
     cik = record
            x, y : Longint;
            adr : ref;
           end;

Var n, m, i, grf : Longint;
    d : array[1..1000] of dreapta;
    v : vector;

Procedure dei( st, dr, i : Integer );
Var vert, cod : boolean;
    mm, nn : real;
    ki, kf, j : Integer;
    e, k1, k2 : ref;
    aux : elm;
Begin
    If ( i > n ) or ( st = dr ) then exit;
    k1 := nil;
    k2 := nil;
    If d[i].b = 0 then
        Begin
            vert := true;
            mm := 0;
            nn := -d[i].c/d[i].a;
        End
        else
        Begin
            vert := false;
            mm := -d[i].a/d[i].b;
            nn := -d[i].c/d[i].b;
        End;
        ki := st-1;
        kf := dr+1;
        For j := st to dr do
            Begin
                Case vert of
                    true: if v[j].x > nn then cod := true
                                          else cod := false;
                    false: if v[j].y < mm*v[j].x + nn then cod := true
                                                       else cod := false;
                End;
                If cod then
                    Begin
                        ki := ki+1;
                        new( e );
                        e^.x := v[j].x;
                        e^.y := v[j].y;
                        e^.adr := k1;
                        k1 := e;
                    End
                    else
                    Begin
                        kf := kf-1;
                        new( e );
                        e^.x := v[j].x;
                        e^.y := v[j].y;
                        e^.adr := k2;
                        k2 := e;
                    End;
            End;
    if ( k1 <> nil  ) and ( k2 <> nil ) then
        Begin
            grf := grf+1;
            e := k1;
            j := st;
            while e <> nil do
                Begin
                    v[j].x := e^.x;
                    v[j].y := e^.y;
                    j := j+1;
                    e := e^.adr;
                End;
            e := k2;
            while e <> nil do
                Begin
                    v[j].x := e^.x;
                    v[j].y := e^.y;
                    j := j+1;
                    e := e^.adr;
                End;

        End;
    while k1 <> nil do
        Begin
            e := k1;
            k1 := k1^.adr;
            dispose( e );
        End;
    while k2 <> nil do
        Begin
            e := k2;
            k2 := k2^.adr;
            dispose( e );
        End;
    dei( st, ki, i+1 );
    dei( kf, dr, i+1 );
End;

Begin
    Assign( input, 'regiuni.in' );
    Reset( input );
        Readln( n, m );
        For i := 1 to n do
            Readln( d[i].a, d[i].b, d[i].c );
        For i := 1 to m do
                Readln( v[i].x, v[i].y );
    Close( input );

    grf := 1;
    dei( 1, m, 1 );

    Assign( output, 'regiuni.out' );
    Rewrite( output );
        Writeln( grf );
    Close( output );

End.