Nu aveti permisiuni pentru a descarca fisierul grader_test16.in
Cod sursa(job #96240)
| Utilizator | Data | 31 octombrie 2007 20:00:43 | |
|---|---|---|---|
| Problema | Hvrays | Scor | 0 |
| Compilator | fpc | Status | done |
| Runda | Arhiva de probleme | Marime | 1.56 kb |
type punct=record
x,y:longint;
end;
type vector=array[1..100010]of punct;
var v,x:vector;
i,j,n,m,k,t,max,nr:longint;
aux:punct;
procedure qsort(ls,ld:longint; var v:vector);
var i,j:longint;
begin
i:=ls;j:=ld;
while true do begin
while ((v[i].y>v[j].y)or((v[i].y=v[j].y)and(v[i].x>=v[j].x)))and(i<>j) do inc(i);
if i=j then break;
aux:=v[i];v[i]:=v[j];v[j]:=aux;dec(j);
while ((v[i].y>v[j].y)or((v[i].y=v[j].y)and(v[i].x>=v[j].x)))and(i<>j) do dec(j);
if i=j then break;
aux:=v[i];v[i]:=v[j];v[j]:=aux;inc(i);
end;
if j-1>ls then qsort(ls,j-1,v);
if j+1<ld then qsort(j+1,ld,v);
end;
begin
assign(input,'hvrays.in');reset(input);
assign(output,'hvrays.out');rewrite(output);
readln(t);
for k:=1 to t do
begin
readln(n,m);
for i:=1 to n do
read(v[i].x,v[i].y);
for i:=1 to m do
read(x[i].x,x[i].y);
qsort(1,n,v);
qsort(1,n,x);
i:=1;
j:=1;
max:=1;
nr:=0;
while (i<=n)and(j<=m) do
begin
j:=max+1;
while x[j].y>=v[i].y do
begin
if x[j].x>x[max].x then
max:=j;
inc(j);
end;
inc(nr);
while (v[i].x<=x[max].x)and(i<=n) do
inc(i);
end;
writeln(nr);
end;
close(input);close(output);
end.