h3. Trapez

Problema a fost cea de nivel mediu din cele $3$ si face apel la cunostiinte minime de geometrie. Conditia ca oricare trei puncte nu sunt coliniare simplifica mult rezolvarea. Din definitie, un trapez are cel putin doua laturi paralele deci se poate construi urmatorul algoritm: se iau toate perechile de puncte - acestea determina cate un segment - si sorteaza in functie de unghiul cu axa OX (panta dreptei). Pentru fiecare $k$ segmente cu acelasi unghi se pot forma {$Comb(k,2)$} trapeze. Pentru a evita calculele cu reale (care pot cauza erori de precizie), se tin pantele ca perechi de numere intregi ({$y, x$}), fara a efectua efectiv impartirea {$y/x$}. Pentru compararea a doua astfel de perechi sunt necesare tipuri de date pe $64$ de biti. Algoritmul descris are complexitate {$O(N^2^*lg N)$}. Las ca exercitiu rezolvarea acestei probleme folosind un algoritm $O(N^2^)$ care foloseste "hashing":http://www.infoarena.ro/Hashing (vezi articolul de pe site). Se puteau obtine $40-50p$ cu un algoritm brut {$O(N^4^)$}.

Problema a fost cea de nivel mediu din cele $3$ si face apel la cunostiinte minime de geometrie. Conditia ca oricare trei puncte nu sunt coliniare simplifica mult rezolvarea. Din definitie, un trapez are cel putin doua laturi paralele deci se poate construi urmatorul algoritm: se iau toate perechile de puncte - acestea determina cate un segment - si sorteaza in functie de unghiul cu axa OX (panta dreptei). Pentru fiecare $k$ segmente cu acelasi unghi se pot forma {$Comb(k,2)$} trapeze. Pentru a evita calculele cu reale (care pot cauza erori de precizie), se tin pantele ca perechi de numere intregi ({$y, x$}), fara a efectua efectiv impartirea {$y/x$}. Pentru compararea a doua astfel de perechi sunt necesare tipuri de date pe $64$ de biti. Algoritmul descris are complexitate {$O(N^2^*lg N)$}. Las ca exercitiu rezolvarea acestei probleme folosind un algoritm $O(N^2^)$ care foloseste "hashing":tabele-hash-scurta-prezentare (vezi articolul de pe site). Se puteau obtine $40-50p$ cu un algoritm brut {$O(N^4^)$}.

h3. Subsir