Geometrie
Autor: drd. Paul Diac, Facultatea de Informatică Iaşi, Universitatea Alexandru Ioan Cuza
Soluţie – 100p – Complexitate O(MlogN)
Se construieşte pas cu pas infăşuratoarea convexă a punctelor din stânga oricarui punct din mulţimea A. La fiecare etapă, avem înfăşuratoarea convexă a punctelor din stânga unei anumite limite x şi se adauga următorul punct din mulimea A, care este cel mai din stânga punct de dupa aceasta limită (din dreapta limitei).
Se răspunde dupa acest pas la toate întrebarile care au coordonata x între cel mai din dreapta punct din mulţimea punctelor procesate din A şi mulţimea punctelor neprocesate înca.
Alte detalii: avem nevoie astfel de două tipuri de operaţii. Pe prima o vom numi ‘update’, reprezintă adăugarea la înfăşuratoare a unui punct din (strict) dreapta înfaşurătorii. Operaţia ‘query’ cere determinarea ariei înfăşurătorii convexe a unei înfăşurători reunite cu un ‘punct de query’, dar acest punct nu va rămâne pe înfăşuratoare decât pentru acest query. Similar cu update, acest punct este în (strict) dreapta infăşurătorii.
Atat pentru update cât şi pentru query trebuie determinate ‘tangentele’ unui punct la un poligon convex deja calculat. Dacă punctele de pe înfăşurătoarea convexă sunt reţinute în două stive (pentru partea superioară şi partea inferioară); in aceste stive se poate itera liniar pentru a găsi punctul tangent la poligon, unde sensul / aria triunghiului cu semn işi schimbă semnul (triunghiul format din ‘punctul de query’ şi două puncte consecutive de pe înfăşurătoare). Deoarece semnul se schimbă de la o poziţie şi se menţine mai departe, se poate căuta binar poziţia, pentru soluţia optimă. Observaţie: pentru query e necesar să căutam binar punctele ‘tangente’, însă pentru update se poate căuta liniar, deoarece punctele iterate vor fi scoase de pe înfăşurătoare o singura dată, deci, aceste operaţii se vor amortiza. Algoritmul pentru partea de update este un algoritm clasic numit Andrew’s algorithm. Punctele sunt reţinute în stive similar ca idee cu algoritmul Graham scan: un update poate elimina de pe înfăşurătoare un număr oarecare de puncte, dar ele vor fi eliminate o singură dată.
Pentru a calcula în timp constant ariile, trebuie precalculată aria “din partea stânga” pentru fiecare punct de pe înfăşurătoarea convexă, de exemplu: aria proiecţiei pe OX a segmentelor de pe înfăşurătoare de la cel mai din stânga punct până la punctul curent, atât pentru punctele de pe stiva superioară cât şi pentru cea inferioară. Evident, când se inserează un punct, aria este suma dintre aria precalculată pentru punctul cu care se învecinează în stânga şi aria trapezului dreptunghic care se află sub acest segment nou. Răspunsul pentru un query este diferenţa ariilor precalculate pentru stiva superioară şi cea inferioară.
Solutie – 80p – Complexitate O(M * N)
Se implementează algorimul descris mai sus, mai puţin căutarea binară (se caută liniar).
Solutie – 60p – Complexitate O(M * NlogN)
Se reconstruieşte complet la fiecare pas (punct Ai de la stânga la dreapta) înfăşuratoarea convexă a punctelor din stânga. Algoritmul de determinare a înfăşurătorii convexe este unul de complexitate O(N log N), de exemplu Graham scan. Aria se calculeaza de fiecare dată în O(N), cu algoritmul clasic.
Solutie – 40p – Complexitate O(M * N2)
Se reconstruieşte la fiecare pas înfăşurătoarea convexă în O(N2), de exemplu folosind algoritmul Javis March (împachetarea pachetului). Aria se calculează de fiecare data în O(N).
Solutie – 20p – pentru N ≤ 3
Poligoanele pentru care trebuie calculată înfăşurătoarea convexă sunt fie triunghiuri, fie patrulatere. Pentru triunghiuri, se poate aplica direct formula pentru aria unui triunghi şi se obţin 10 din cele 20 puncte doar cu atât. Pentru patrulatere, înfăşuratoarea convexă poate fi un triunghi sau un patrulater şi trebuie tratate corect ambele cazuri.
