h2. Pentru 100 de puncte

Putem calcula $urm[i]$ = punctul urmator din poligon pe care trebuie sa il pastrez daca pastrez punctul $i$. Datorita faptului ca poligonul este convex, $urm[i + 1]$ este fie $urm[i]$, fie mai incolo in sens trigonometric. Calculul sirului $urm[]$ se poate realiza in $O(N)$.

Putem calcula $urm[i]$ = punctul urmator din poligon pe care trebuie sa il pastrez daca pastrez punctul $i$. Datorita faptului ca poligonul este convex, $urm[i + 1]$ este fie $urm[i]$, fie mai incolo in sens trigonometric. Calculul sirului $urm[]$ se poate realiza in $O(N)$. Acest lucru e posibil tocmai pentru ca: _Se garanteaza ca in situatia in care se pastreaza toate barele, pisica se poate roti/translata succesiv astfel incat sa atinga orice bara cu orice varf al ei._

Apoi putem folosi aceste salturi pentru a putea obtine rapid solutia optima in complexitate mai buna. De exemplu, putem tine $d[i][j]$ = cat de mult ma extind in sens trigonometric daca fac $2^i^$ salturi de forma $x -> urm[x]$ daca plec din $j$. Initializarea este $d[ 0 ][i] = distantaTrigonometrica(i -> urm[i])$ iar recurenta se realizeaza in $O(1)$. Dupa aceasta precalculare de $O(N * logN)$, putem afla in $O(logN)$ care este numarul de puncte pe care trebuie sa le pastrez daca aleg sa il pastrez neaparat pe $i$. Luand pe rand toate valorile posibile ale lui $i$, aflam solutia optima.

private

protected