 DREPTUNGHIURI
Concursul e_mail, Oradea 1997

        Fie n dreptunghiuri, cu laturile paralele cu axele de coordonate, date
prin elementele "colt stanga sus" (xs, ys) si "colt dreapta jos" (xd, yd). Sa
se precizeze dreptunghiurile care se intersecteaza.
        Citirea se face din fisierul "din" avand structura:

1 xs1 ys1 xd1 yd1
2 xs2 ys2 xd2 yd2
................
n xsn ysn xdn ydn

unde:
1, 2, ..., n     reprezinta numerele de ordine ale dreptunghiurilor
xsi ysi xdi ydi  reprezinta coordonatele "colt stanga sus", "colt dreapta
                 jos" dreptunghiului "i"

        Afisarea se face in fisierul "drez" care contine n linii de forma:

i d1 d2 d3 ... dk

cu semnificatia: dreptunghiul i se intersecteaza cu dreptunghiurile
                 d1, d2, ..., dk


Observatii:      0 <= n <= 100
^^^^^^^^^^^      0 <= xsi, ysi, xdi, ydi <= 1000  (intregi)
                 doua dreptunghiuri se intersecteaza daca:
                        - cel putin cate o latura se intersecteaza;
                        - au un cel putin un varf comun;
                        - au cel putin o latura comuna;
                 daca dreptunghiul i nu se intersecteaza cu nici un alt
                 dreptunghi, atunci pe linia respectiva va aparea scris
                 doar "i"
Exemplu:
^^^^^^^^
Fie fisierul "din":

1 1 6 10 1
2 2 9 4 5
3 8 11 13 6
4 13 4 15 2
5 5 9 17 3
6 4 16 5 14

Fisierul "drez" va fi:

1 2 3 5
2 1
3 1 4 5
4 5
5 1 3 4
6
Timp de executie 30 secunde/test (586 la 133MHz)
======================================
Solutie (Adrian carcu)

uses graph;
var fis:text;
    x1,y1,x2,y2:array[1..100] of integer;
    a:array[1..100,1..100] of byte;
    n,i,j,gd,gm:integer;

function intre(a,b,n:integer):boolean;
begin
   if (b-n)*(n-a)>=0 then intre:=true else intre:=false;
end;

function interv(a,b,c,d:integer):boolean;
begin
   if intre(a,b,c) or intre(a,b,d) or intre(c,d,a) or intre(c,d,b)
      then interv:=true else interv:=false;
end;

function inters(i,j:integer):boolean;
begin
   if interv(x1[i],x2[i],x1[j],x2[j]) and interv(y1[i],y2[i],y1[j],y2[j])
      then inters:=true else inters:=false;
end;

procedure desen(i,j:integer);
begin
   cleardevice;
   if a[i,j]=1 then circle(100,100,10);
   rectangle(x1[i]*10,y1[i]*10,x2[i]*10,y2[i]*10);
   rectangle(x1[j]*10,y1[j]*10,x2[j]*10,y2[j]*10);
   asm xor ah,ah; int 16h; end;
end;

begin
   {gd:=vga; gm:=vgahi; initgraph(gd,gm,'c:\bp\bgi');}
   assign(fis,'dreptung.dat'); reset(fis);
   n:=0;
   while not eof(fis) do begin
      inc(n);
      read(fis,i);
      readln(fis,x1[i],y1[i],x2[i],y2[i]);
      end;
   close(fis);
   for i:=1 to n-1 do
      for j:=i+1 to n do
         if inters(i,j) then begin a[i,j]:=1; a[j,i]:=1; end
                        else begin a[i,j]:=0; a[j,i]:=0; end;
   for i:=1 to n do begin
      write(i,' ');
      for j:=1 to n do begin
         {if i<>j then desen(i,j);}
         if (i<>j) and (a[i,j]=1) then write(j,' ');
         end;
      writeln;
      end;
   {closegraph;}
end.
-----------------------------
