Dupa cum au aratat-o si rezultatele, aceasta problema a fost cea mai simpla din concurs. Trebuie sa determinam numarul de dreptunghiuri a caror laturi nu intalnsesc laturile altor dreptunghiuri. De asemenea, sa nu uitam ca dreptunghiurile nu se pot suprapune. In aceste conditii observam ca daca doua dreptunghiuri se intersecteaza atunci se vor intersecta si $2$ segmente verticale sau $2$ segmente orizontale. Putem astfel sa luam mai intai toate segmentele verticale, vedem care dintre acestea se intersecteaza cu altele si marcam dreptunghiurile lor ca fiind rele. Repetam algoritmul si pentru segmentele orizontale, iar la sfarsit numaram cate dreptunghiuri bune ne-au ramas.

Problema pe care trebuie sa o rezolvam acum este urmatoarea: avand $K$ segmente paralele cu axa Oy trebuie sa determinam care dintre acestea se intersecteaza cu altele. Pentru aceasta sortam segmentele in primul rand dupa coordonata $x$ si in al 2-lea rand dupa coordonata $y$ minima. Dupa aceasta sortare putem determina in $O(K)$ segmentele care se intersecteaza. Parcurgem vectorul de la stanga la dreapta, si pentru fiecare pas vedem daca segmentul curent se intersecteaza cu un segment precedent. Pentru aceasta trebuie sa tinem o variabila ls care reprezinta coordonata $y$ maxima atinsa pana la un moment dat. Pentru segmentul $i$ fie {$ymin{~i~}$}, $ymax{~i~}$ si $x{~i~}$ coordonatele lui. Pentru un $i$ daca $x{~i~} != x{~i-1~}$ sau $ymin{~i~} > ls$ initializam $ls$ cu {$ymax{~i~}$}. Altfel marcam segmentul $i$ si segmentul cu care am obtinut maximul $ls$ ca fiind rele, iar $ls$ devine {$MAX(ls, ymax{~i~})$}.

Problema pe care trebuie sa o rezolvam acum este urmatoarea: avand $K$ segmente paralele cu axa Oy trebuie sa determinam care dintre acestea se intersecteaza cu altele. Pentru aceasta sortam segmentele in primul rand dupa coordonata $x$ si in al 2-lea rand dupa coordonata $y$ minima. Dupa aceasta sortare putem determina in $O(K)$ segmentele care se intersecteaza. Parcurgem vectorul de la stanga la dreapta, si pentru fiecare pas vedem daca segmentul curent se intersecteaza cu un segment precedent. Pentru aceasta trebuie sa tinem o variabila ls care reprezinta coordonata $y$ maxima atinsa pana la un moment dat. Pentru segmentul $i$ fie {$ymin{~i~}$}, $ymax{~i~}$ si $x{~i~}$ coordonatele lui. Pentru un $i$ daca $x{~i~} != x{~i-1~}$ sau $ymin{~i~} > ls$ initializam $ls$ cu {$ymax{~i~}$}. Altfel marcam segmentul $i$ si segmentul cu care am obtinut maximul $ls$ ca fiind rele, iar $ls$ devine {$MAX (ls, ymax{~i~})$}.

Problema se rezolva similar si pentru segmentele orizontale. Complexitatea algoritmului este {$O(N logN)$}.