h2. Popandai

Popandai
 

(problema grea clasele 11-12)

Mai intai vom calcula, pentru fiecare pereche de puncte $A$ si $B$ din punctele ce reprezinta vizuinele, in sirul $sub{~AB~}$ cate puncte din restul de $n$ se afla sub segmentul de dreapta determinat de $A$ si $B$. Aceasta preprocesare poate fi efectuata in $O(n^2^ log n)$ cu un algoritm inteligent sau poate fi efectuata in $O(n^3^)$ cu metoda naiva care verifica pentru fiecare punct daca este situat pe intervalul $[A.x, B.x]$ si este sub dreapta determinata de cele doua puncte. Preprocesare vom putea pentru fiecare triunghi $ABC$ sa aflam in timp $O(1)$ cate puncte are in interior: presupunem fara a restrange generalitatea ca $A.x ≤ B.x ≤ C.x$, daca punctul $B$ e deasupra dreptei $AC$ atunci numarul de puncte din interiorul lui $ABC$ este $sub{~AB~} + sub{~BC~} - sub{~AC~}$, iar daca $B$ este sub dreapta $AC$ atunci numarul de puncte este $sub{~AC~} - sub{~AB~} - sub{~BC~} - 1$.

Mai intai vom calcula, pentru fiecare pereche de puncte A si B din punctele ce reprezinta vizuinele, in sirul sub[AB] cate puncte din restul de n se afla sub segmentul de dreapta determinat de A si B. Aceasta preprocesare poate fi efectuata in O(n^2 log n) cu un algoritm inteligent sau poate fi efectuata in O(n^3) cu metoda naiva care verifica pentru fiecare punct daca este situat pe intervalul [A.x, B.x] si este sub dreapta determinata de cele doua puncte. Preprocesare vom putea pentru fiecare triunghi ABC sa aflam in timp O(1) cate puncte are in interior: presupunem fara a restrange generalitatea ca A.x <= B.x <= C.x, daca punctul B e deasupra dreptei AC atunci numarul de puncte din interiorul lui ABC este sub[AB] + sub[BC] - sub[AC], iar daca B este sub dreapta AC atunci numarul de puncte este sub[AC] - sub[AB] - sub[BC] - 1.

Orice patrulater, fie el concav sau convex, are o diagonala interna. Daca fixam un segment $PQ$ ca fiind diagonala interna putem sa incercam sa gasim pentru fiecare $x$ triunghiul $PQR$ de arie minima pentru care punctul $R$ este deasupra dreptei $PQ$ si care contine in interior cel putin $x$ puncte, iar apoi sa gasim un triunghi $PQS$ de arie minima cu varful $S$ sub dreapta $PQ$ ce contine in interior cel putin $k-x$ puncte. Ariile minime ale acestor triunghiuri se pastreaza in doua siruri over si under iar aria minima a unui patrulater cu o diagonala $PQ$ va fi $min(over{~x~} + under{~k-x~} | unde x ia toate valorile de la 0 la k)$. Folosind artificiul explicat mai sus putem determina in $O(1)$ numarul de puncte ce se afla in interiorul unui triunghi, si astfel sirurile $over$ si $under$ pot fi calculate in $O(n)$. Complexitatea totala a algoritmului este $O(n^3^)$ pentru ca avem $O(n^3^)$ calcule in faza de preprocesare si pentru fiecare $n(n-1)/2$ diagonale vom efectua $O(n)$ calcule.

Orice patrulater, fie el concav sau convex, are o diagonala interna. Daca fixam un segment PQ ca fiind diagonala interna putem sa incercam sa gasim pentru fiecare x triunghiul PQR de arie minima pentru care punctul R este deasupra dreptei PQ si care contine in interior cel putin x puncte, iar apoi sa gasim un triunghi PQS de arie minima cu varful S sub dreapta PQ ce contine in interior cel putin k-x puncte. Ariile minime ale acestor triunghiuri se pastreaza in doua siruri over si under iar aria minima a unui patrulater cu o diagonala PQ va fi min(over[x] + under[k-x] | unde x ia toate valorile de la 0 la k). Folosind artificiul explicat mai sus putem determina in O(1) numarul de puncte ce se afla in interiorul unui triunghi, si astfel sirurile over si under pot fi calculate in O(n). Complexitatea totala a algoritmului este O(n^3) pentru ca avem O(n^3) calcule in faza de preprocesare si pentru fiecare n(n-1)/2 diagonale vom efectua O(n) calcule.

References