h2(#poligon3). 'Poligon3':problema/poligon3

Vom fixa pe rând fiecare punct din cele $N$ date ca cel mai din stânga şi, în caz de egalitate, cel mai de sus punct ce poate fi pe poligon. După ce am fixat un anume punct de referinta, ne mai interesează doar punctele cu absicsa strict mai mare sau cu abscisa mai mare sau egala si ordonata strict mai mica ca a punctului fixat. Notam punctul de referinta cu $0$. Sortam punctele ramase in functie de panta segmentului pe care il formeaza cu punctul de referinta. Vom parcurge punctele ramase in aceasta ordine si folosind metoda programarii dinamice vom construi o matrice $C[i][j]$ = aria maxima a unui poligon care are ultimele doua puncte $j$ si $i$. Recurenta este $C[i][j] = max{C[j][k] + Arie(0, i, j) | i, j, k pastreaza forma convexa a poligonului si triunghiul 0, i, j nu contine nici un alt punct}$. Testul de pastrare a convexitatii este explicat pe larg in acest "articol":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1. Verificarea ca triunghiul $0, i, j$ sa nu contina nici un punct se poate face in $O(1)$ cu ajutorul unei preprocesari, conducand la o complexitate totala de $O(N^4^)$.

Vom fixa pe rând fiecare punct din cele $N$ date ca cel mai din stânga şi, în caz de egalitate, cel mai de sus punct ce poate fi pe poligon. După ce am fixat un anume punct de referinţă, ne mai interesează doar punctele cu absicsa strict mai mare sau cu abscisa mai mare sau egală şi ordonata strict mai mică ca a punctului fixat. Notăm punctul de referinţă cu $0$. Sortăm punctele rămase în funcţie de panta segmentului pe care îl formează cu punctul de referinţă. Vom parcurge punctele rămase în această ordine şi folosind metoda programării dinamice vom construi o matrice $C[i][j] =$ aria maximă a unui poligon care are ultimele două vârfuri în punctele $j$ şi $i$. Recurenţa este $C[i][j] = max{C[j][k] + Arie(0, i, j) | i, j, k păstrează forma convexă a poligonului şi triunghiul (0, i, j) nu conţine nici un alt punct în interior}$. Testul de păstrare a convexităţii este explicat pe larg în acest "articol":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1. Verificarea ca triunghiul $0, i, j$ să nu conţină nici un alt punct se poate face in $O(1)$ cu ajutorul unei preprocesari, conducând la o complexitate totală de $O(N^4^)$.
Pentru a obţine complexitatea $O(N^3^)$, vom modifica semnificaţia matricii astfel: $C[i][j] = $ aria maxima a unui poligon ce are ultimul vârf în punctul $i$ şi penultimul vârf în unul dintre punctele dintre $1$ şi $j$. Având un punct $i$ fixat ca ultimul vârf al poligonului până în momentul respectiv, vom determina acele puncte $j$ pentru care triunghiul $(0, i, j)$ nu conţine nici un punct în interior. Punctul $i-1$ se află mereu printre aceste puncte $j$, deoarece este imposibil să existe vreun punct în triunghiul $(0, i-1, i)$ din cauza sortării iniţiale. Apoi vom determina restul punctelor $j$ cu o parcurgere în ordine inversă şi bazându-ne pe observaţia ca următorul punct $j$ pe care îl vom determina va verifica testul de păstrare al convexităţii relativ la punctul $i$ şi la ultimul punct de tip $j$ pe care l-am determinat pâna acum. Punem toate aceste puncte $j$ in multimea $s$ în ordinea sortării (sau în ordinea inversă determinării lor). Recurenţa devine $C[i][s{~k~}] = max{C[i][s{~k-1~}], C[s{~k~}][s{~k-1~}] + Arie(0, s{~k~}, i)}$.

private

public