Fişierul intrare/ieşire:	infasuratoare.in, infasuratoare.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	dragus marius •mariusdrg
Timp execuţie pe test	0.25 sec	Limită de memorie	24096 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Infasuratoare convexa

Dandu-se un set de N puncte in plan, sa se determine poligonul convex de arie minima care are in interiorul lui sau pe margini toate punctele.

Date de intrare

În fişierul de intrare infasuratoare.in se va gasi pe prima linie N, care reprezinta numarul de puncte. Pe urmatoarele N linii se vor gasi doua numere rationale X_i, Y_i care reprezinta coordonatele punctului i.

Date de ieşire

În fişierul de ieşire infasuratoare.out va fi, pe prima linie, numarul de puncte de pe infasuratoarea convexa. Pe urmatoarea linie se va afla cel mai de jos si in caz de egalitate cel mai din stanga punct de pe infasuratoare, decris prin coordonate X si Y. Pe urmatoarele linii, pana la sfarsitul fisierului se vor gasi 2 numere reale reprezentand varfurile poligonului in ordine invers trigonometrica.

Restricţii

• -1.000.000.000 ≤ X_i,Y_i ≤ 1.000.000.000
• Pentru 20% din teste N ≤ 20
• Pentru inca 60% din teste N ≤ 120.000.
• Pentru ultimele 20% din teste N ≤ 1.100.000 si punctele vor fi sortate dupa X si in caz de egalitate dupa Y.

Exemplu

Indicatii de rezolvare

Acest poligon se mai numeste si infasuratoarea convexa a punctelor.
Pentru usurinta intelegerii rezolvarii se face urmatoarea notatie: notam H ca fiind numarul de varfuri ale infasuratorii convexe.
O prima observatie esentiala este ca varfurile acestui poligon sunt puncte din acele N puncte date initial. 
Cu aceasta observatie se poate implementa urmatorul algoritm naiv si usor de implementat. Se incepe cu un punct care se afla sigur pe infasuratoare, sa presupun ca il alegem pe cel mai de jos si in caz de egalitate cel mai din stang. Dupa ce s-a ales acest punct se incearca toate punctele si se alege punctul care face o intoarcere cat mai puternica spre stanga cu punctul curent, aceasta se face in O(N). Acest punct la randul lui se afla pe infasuratoare deoarece nu exista nici un alt punct care unit cu primul sa il acopere. Se continua algoritmul cu punctul tocmai ales. Aceasta solutie face O(N) pasi pentru fiecare punct de pe infasuratoare convexa, deci complexitatea finala ar fi O(N*H). In caz general, pentru teste generate random aceasta solutie face un numar mic de pasi, dar pentru teste generate inteligent poate face aproximativ O(N²) pasi. Aceast algoritm se numeste Jarvis March. O sursa se poate vedea aici.
O alta solutie se bazeaza pe sortarea dupa unghi. Se alege un punct care sa fie sigur pe infasuratoare, sa presupunem ca e cel mai de jos punct. Se sorteaza toate punctele in functie de panta dreptei care uneste punctul ales de restul punctelor. Dupa care se construieste o stiva care tine in fiecare moment infasuratoare convexa curenta. Un punct cand este introdus in stiva va scoate puncte pana cand acesta formeaza cu dreapta definita de ultimele 2 puncte din stiva un unghi mai mic de 180 grade, si astfel se tot inchide poligonul. Acest algoritm se numeste Graham Scan. Complexitatea sortarii este O(Nlog₂N) iar complexitatea stivei este de O(N), complexitatea totala fiind de O(NlogN + N).
Aceasta este complexitatea teoretica optima pe caz general. O astfel de implementare se poate vedea aici.
O alta solutie care are complexitate tot O(Nlog₂N), dar care se poate imbunatati, este compusa din urmatorii pasi:
* Se sorteaza punctele dupa x iar in caz de egalitate dupa y
* Se alege cel mai de jos punct si cel mai de sus punct si se desparte in 2 subprobleme. Pe fiecare parte a dreptei trebuie sa fie gasita infasuratoarea. Aceasta se realizeaza cu o stiva foarte asemanatoare cu cea prezentata anterior. Cat timp pe ambele parti ale dreptei este respectata convexitatea si ambele parti incep si se termina cu punctele alese(cel mai de jos si cel mai de sus) si , din cauza stivei, cuprind toate punctele, reuninuea lor va reprezenta infasuratoarea convexa.
O astfel de solutie este compusa din 2 pasi unul, sortarea, avand complexitate generala O(Nlog₂N), si dupa 2 stive ambele cu complexitate O(N). O optimizare care se poate aduce deobicei la algoritmul acesta in timp de concurs este ori ca punctele sunt direct sortate, cum este cazul de fata, sau ca punctele au coordonate intregi , moment in care se poate apela la o sortare care se bazeaza pe limitarea capacitatii calculatorului de a tine minte numere intregi foarte mari gen Radix Sort sau cateodata Counting Sort. O astfel de solutie se poate vedea aici.
O alta prezentare a acestei probleme este aceea cand punctele nu sunt toate date deodata, iar fiecare punct este prezentat iterativ. Este destul de clar ca la oricare algoritm dintre cele prezentate pana acum mai apare un N la complexitate, lucru care le face in mare parte ineficiente si inutile pentru problema aceasta
Un algoritm naiv cu complexitate O(N*H) se poate realiza daca la fiecare aparitie a unui punct se verifica daca acesta este sau nu in poligon. Daca este in poligon nu mai trebuie modificat nimic. Daca nu atunci se cauta primul punct din poligon care unit cu punctul curent nu trece prin interiorul poligonului. Se determina toate aceste puncte si se scot din poligon, dupa care se introduce punctul nou in locul celor scoase.
O observatie matematica care ajuta la optimizarea acestui algoritm este faptul ca in functie de un punct din interiorul poligonului, varfurile par sa fie sortate in functie de unghi, si astfel cautarea unui punct care trebuie scos se reduce la o cautare binara de complexitate O(Nlog₂H). Secventa de puncte care trebuie scoase sunt un interval compact mereu si astfel dupa ce se gaseste primul punct se pot determina toate punctele care trebuie scoase in o singura parcurgere a lor. Dar acum mai trebuie o structura de date care permite stergere,inserare si cautare in O(log~2~N). O astfel de structura de date este Arborele Echilibrati de cautare, dar care spre norocul nostru sunt implementati deja in stl sub forma de set-uri. O astfel de solutie are complexitate O(Nlog₂N).
Mai trebuie mentionat ca cea mai buna complexitate practica descoperita pana la momentul scrierii acestui articol este O(Nlog₂H), dar si aceasta complexitate teoretic este O(Nlog₂N).

Cum se trimit solutii?