summer-challenge-2009/solutii/runda-3/poligon3

Soluție Poligon 3

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 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^)$.