Cod sursa(job #37638)

Utilizator Bluedrop_demonPandia Gheorghe Bluedrop_demon Data 25 martie 2007 11:34:13
Problema Regiuni Scor 10
Compilator fpc Status done
Runda preONI 2007, Runda 4, Clasa a 10-a Marime 3.69 kb
{
    Problema regiuni
}

Program regiuni;

Type dreapta = record
                a, b, c : Integer;
               end;
     ref = ^elm;
     elm = record
            x, y : Integer;
            adr : ref;
           end;

Var n, m, i, j, k, kf : Integer;
    d : array[1..1000] of dreapta;
    l : array[1..4000] of ref;
    e, f, g : ref;
    mm, nn : real;
    vert, cod : boolean;

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 );
        k := 1;
        l[k] := nil;
        For i := 1 to m do
            Begin
                new( e );
                Readln( e^.x, e^.y );
                e^.adr := l[k];
                l[k] := e;
            End;
    Close( input );

    For i := 1 to n do
        Begin
            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;
            kf := k;
            For j := 1 to kf do
                Begin
                    k := k+1;
                    l[k] := nil;
                    e := l[j];
                    while e <> nil do
                        Begin
                            Case vert of
                                true: if e^.x > nn then cod := true
                                                   else cod := false;
                                false: if e^.y < mm*e^.x + nn then cod := true
                                                              else cod := false;
                            End;
                            If cod = true then
                                        Begin
                                            new( f );
                                            f^.x := e^.x;
                                            f^.y := e^.y;
                                            f^.adr := l[k];
                                            l[k] := f;
                                            If e = l[j] then
                                                Begin
                                                    l[j] := l[j]^.adr;
                                                    dispose( e );
                                                    e := l[j];
                                                End
                                                else
                                                Begin
                                                    g^.adr := e^.adr;
                                                    dispose( e );
                                                    e := g^.adr
                                                End;
                                        End
                                        else
                                        Begin
                                            g := e;
                                            e := e^.adr;
                                        End;
                        End;
                    if l[k] = nil then k := k-1;
                End;
        End;

    kf := 0;
    For i := 1 to k do
        if l[i] <> nil then kf := kf +1;


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

    For i := 1 to k do
        While l[i] <> nil do
            Begin
                e := l[i];
                l[i] := l[i]^.adr;
                dispose( e );
            End;
End.