Cod sursa(job #96246)

Utilizator CezarMocanCezar Mocan CezarMocan Data 31 octombrie 2007 20:20:16
Problema Hvrays Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.89 kb
type punct=record
                x,y:longint;
                end;
type vector=array[0..100010]of punct;

var v,x:vector;
    i,j,n,m,k,t,max,nr,p1,p2: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);
randomize;
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);
{        for i:=1 to 10000 do
                begin
                p1:=random(n)+1;
                p2:=random(n)+1;
                aux:=v[p1];v[p1]:=v[p2];v[p2]:=aux;
                p1:=random(m)+1;
                p2:=random(m)+1;
                aux:=x[p1];x[p1]:=x[p2];x[p2]:=aux;
                end;        }
        qsort(1,n,v);
        qsort(1,m,x);
        i:=1;
        j:=1;
        max:=1;
        nr:=0;
        while (i<=n) 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.