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

Cosmin, observatii: merita mentionat ca in puncte distribuite uniform aleator numarul de puncte de pe infasuratoarea convexa este O(log n). Partea cu construirea incrementala a infasuratorii cuonvexe poate merita pusa in un articol nu in problema in care inveti tehnica. Daca vrem sa discutam de probleme inrudite am putea zice de onion peeling (http://www.docstoc.com/docs/2690112/Introduction-to-Convex-Hull-Applications) care s-a dat si la ginfo.

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. Poligonul astfel obtinut se numeste infasuratoarea convexa a celor N puncte.

Date de intrare

În fişierul de intrare infasuratoare.in se va gasi pe prima linie un numar natural N, care reprezinta numarul de puncte din set. Pe fiecare din urmatoarele N linii se va gasi o pereche de numere rationale X_i, Y_i care reprezinta coordonatele punctului i.

Date de ieşire

Pe prima linie a fişierului de ieşire infasuratoare.out se va afla H, numarul de puncte de pe infasuratoarea convexa. Pe urmatoarele H linii se vor gasi cele H puncte ce alcatuiesc poligonul, in ordine invers trigonometrica, incepand cu cel mai de jos (punctul cu ordonata minima), iar in caz de egalitate cu cel mai din stanga (punctul cu abscisa minima).

Restricţii

• -1.000.000.000 ≤ X_i,Y_i ≤ 1.000.000.000
• 1 ≤ N ≤ 120.000
• 50% din teste sunt generate aleator si astfel au putine puncte pe infasuratoare

Exemplu

Indicaţii de rezolvare

Fie H numarul de varfuri al infasuratorii convexe. O prima observatie esentiala este ca varfurile poligonului solutie sunt puncte din setul celor 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 presupunem ca il alegem pe cel mai de jos si in caz de egalitate pe cel mai din stanga. Dupa ce s-a ales acest punct se incearca toate punctele si se alege punctul care face o intoarcere de unghi maxim spre stanga cu punctul curent. Acest pas se poate face in O(N). Punctul nou determinat se afla la randul lui pe infasuratoare deoarece nu exista niciun alt punct care unit cu primul sa il acopere. Se repeta pasul anterior, de fiecare data cu ultimul punct ales, pana cand ajungem din nou la punctul de pornire. Aceasta solutie face O(N) pasi pentru fiecare punct de pe infasuratoare convexa, deci complexitatea finala este O(N*H). Pe teste generate aleator aceasta solutie face un numar mic de operatii deoarece H este mic in comparatie cu N, dar pentru teste generate inteligent, cand H este de ordinul O(N), algoritmul executa O(N²) pasi. Mai trebuie mentionat ca pentru puncte generate uniform numarul de puncte de pe infasuratoare tinde spre O(log₂N). Aceast algoritm este cunoscut ca potrivirea lui Jarvis, sau impachetarea pachetului. O sursa folosind acest algoritm se poate vedea aici, si obtine 50 de puncte.

O alta solutie se bazeaza pe sortarea dupa unghi. Se alege un punct care sa fie sigur pe infasuratoare: cel mai de jos punct, iar in caz de egalitate cel mai din stanga. Se sorteaza toate punctele in functie de panta dreptei care uneste punctul ales de restul punctelor (unghiul polar), dupa care se construieste o stiva care retine in fiecare moment infasuratoare convexa curenta. Atunci cand un punct 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 de grade. Repetand procedeul pentru fiecare punct se va inchide poligonul. Acest algoritm se numeste scanarea Graham. Complexitatea sortarii punctelor va fi O(Nlog₂N), iar complexitatea construirii propriu-zise a poligonului va fi liniara, deoarece fiecare pas are complexitatea O(1) amortizat. Complexitatea finala va fi deci O(Nlog₂N). Un dezavantaj major al Graham scanului este sortare dupa unghi care poate produce erori de precizie. O modalitate de sortare cu erori de precizie mici se poate vedea in sursa.

O alta solutie care are complexitate tot O(Nlog₂N), dar care se poate imbunatati, este compusa din urmatorii pasi:

• Se sorteaza punctele dupa y, iar in caz de egalitate dupa x
• Se alege cel mai de jos punct si cel mai de sus punct si se desparte problema in 2 subprobleme similare. 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 implementare 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 este un interval compact mereu si, astfel, dupa ce se gaseste primul punct se pot determina toate punctele care trebuie scoase printr-o singura parcurgere a lor. Deoarece poligonul poate doar sa se mareasca pe masura ce se introduc puncte, orice punct care se afla in poligon cand este la inceput(la primele 3 puncte) se va afla tot timpul, astfel un punct care se afla mereu in interiorul poligonului este centrul de greutate initial. Dar acum mai trebuie o structura de date care permite stergere, inserare si cautare in O(log₂N). O astfel de structura de date este Arborele Echilibrati de cautare, care este implementata deja in stl sub forma de set-uri. O astfel de solutie are complexitate O(Nlog₂N).

Aplicaţii

Determinarea infasuratorii convexe reprezinta un algoritm fundamental in geometria computationala. Multe probleme dificile pornesc de la construirea acestui poligon. Printre problemele ce folosesc algoritmii descrisi mai sus, amintim:

• Wall
• How Far Can We Go
• Forum
• Rubarba
• Gradina

Cum se trimit solutii?