Pagini recente » Cod sursa (job #494984) | Cod sursa (job #636044) | Cod sursa (job #1685937) | Cod sursa (job #1799507) | Cod sursa (job #41749)
Cod sursa(job #41749)
{
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.