Diferente pentru problema/infasuratoare intre reviziile #50 si #80

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="infasuratoare") ==
*Cosmin, observatii:* 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.
h2. Date de intrare
h2. 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 din stanga (punctul cu abscisa minima), iar in caz de egalitate cu cel mai de jos (punctul cu ordonata minima).
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 trigonometrica.
h2. Restricţii
* $3 ≤ N ≤ 120.000$
* $-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
* Se recomanda lucrul cu o precizie de {$10^-12^$} pentru lucrul cu numere reale
* Nu vor exista puncte coliniare pe infasuratoarea convexa.
h2. Exemplu
4.0 2.0
4.0 4.0
|6
0.000000 2.000000
0.000000 4.000000
2.000000 6.000000
4.000000 4.000000
4.000000 2.000000
2.000000 0.000000
4.000000 2.000000
4.000000 4.000000
2.000000 6.000000
0.000000 4.000000
0.000000 2.000000
|
h2. 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, concepem 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 din stanga si in caz de egalitate pe cel mai de jos. 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 uniform aleator aceasta solutie face un numar mic de operatii deoarece $H$ este comparabil cu $log{~2~}N$, dar pentru teste generate inteligent, cand $H$ este de ordinul {$O(N)$}, algoritmul executa $O(N^2^)$ pasi. Aceast algoritm este cunoscut ca "potrivirea lui Jarvis":http://www.cs.princeton.edu/~ah/alg_anim/version1/JarvisMarch.html, sau {_impachetarea pachetului_}. O sursa folosind acest algoritm se poate vedea 'aici':job_detail/237253?action=view-source, si obtine $50$ de puncte.
Cu aceasta observatie, concepem 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 din stanga si in caz de egalitate pe cel mai de jos. 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 uniform aleator aceasta solutie face un numar mic de operatii deoarece $H$ este comparabil cu $log{~2~}N$, dar pentru teste generate inteligent, cand $H$ este de ordinul {$O(N)$}, algoritmul executa $O(N^2^)$ pasi. Aceast algoritm este cunoscut ca "Jarvis' March":http://www.cs.princeton.edu/~ah/alg_anim/version1/JarvisMarch.html sau {_impachetarea pachetului_}. O sursa folosind acest algoritm se poate vedea 'aici':job_detail/239592?action=view-source
!> problema/infasuratoare/?pic2.bmp!
O alta solutie se bazeaza pe sortarea dupa unghi. Se alege un punct care sa fie sigur pe infasuratoare: cel mai din stanga punct, iar in caz de egalitate cel mai de jos. 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":http://www.cs.princeton.edu/~ah/alg_anim/version1/GrahamScan.html. Complexitatea sortarii punctelor va fi {$O(Nlog{~2~}N)$}, iar complexitatea construirii propriu-zise a poligonului va fi liniara, deoarece fiecare pas are complexitatea {$O(1)$} amortizat, fiecare punct intrand si iesind din stiva maxim o data. Complexitatea finala va fi deci $O(Nlog{~2~}N)$. Un dezavantaj al acestui algoritm este sortarea dupa unghi, care poate produce erori de precizie. O modalitate de sortare cu erori de precizie mici se poate observa 'aici':job_detail/237284?action=view-source.
O alta solutie se bazeaza pe sortarea dupa unghi. Se alege un punct care sa fie sigur pe infasuratoare: cel mai din stanga punct, iar in caz de egalitate cel mai de jos. 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":http://en.wikipedia.org/wiki/Graham_scan. Complexitatea sortarii punctelor va fi {$O(Nlog{~2~}N)$}, iar complexitatea construirii propriu-zise a poligonului va fi liniara, deoarece fiecare pas are complexitatea {$O(1)$} amortizat, fiecare punct intrand si iesind din stiva maxim o data. Complexitatea finala va fi deci $O(Nlog{~2~}N)$. Un dezavantaj al acestui algoritm este sortarea dupa unghi, care poate produce erori de precizie. O modalitate de sortare cu erori de precizie mici se poate observa 'aici':job_detail/800758?action=view-source.
O alta solutie care are complexitate tot $O(Nlog{~2~}N)$, dar care se poate imbunatati in functie de particularitatile problemei, este compusa din urmatorii pasi:
*  Se sorteaza punctele dupa {$x$}, iar in caz de egalitate dupa $y$
*  Se aleg cel mai din stanga si cel mai din dreapta punct si se desparte problema in $2$ subprobleme similare. Pe fiecare parte a dreptei determinata de cele doua puncte trebuie sa fie gasita infasuratoarea. Aceasta se realizeaza cu o stiva foarte asemanatoare cu cea prezentata anterior. Cat timp de ambele parti ale dreptei este respectata convexitatea si ambele parti incep si se termina cu punctele alese (cel mai din stanga si cel mai din dreapta), reuninuea lor va reprezenta infasuratoarea convexa a tuturor punctelor.
O astfel de implementare se poate vedea 'aici':job_detail/237301?action=view-source.
O astfel de implementare se poate vedea 'aici':job_detail/731548?action=view-source.
O optimizare care se poate aduce este atunci cand punctele au coordonate intregi, cand putem folosi in pasul de sortare algoritmi precum "Radix Sort":http://en.wikipedia.org/wiki/Radix_sort sau, uneori, "Counting Sort":http://en.wikipedia.org/wiki/Counting_sort. In plus, daca punctele sunt direct sortate, complexitatea devine {$O(N)$}.
* "Wall":http://acm.tju.edu.cn/toj/showp.php?pid=2317
* "How Far Can We Go":http://acm.tju.edu.cn/toj/showp.php?pid=2847
* "Dragon":http://campion.edu.ro/problems/3/338/dragon_ro.htm
* "Forum":http://campion.edu.ro/problems/3/468/forum_ro.htm
* 'Rubarba':problema/rubarba
* 'Gradina':problema/gradina
* 'Mosia':problema/mosia
== include(page="template/taskfooter" task_id="infasuratoare") ==
 
== include(page="template/taskfooter" task_id="infasuratoare") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3540