Analiza

Zadatak rešavamo dinamičkim programiranjem. Rešimo prvo zadatak u slučaju da su sve koordinate $Y_i$ pozitivne. Prvo sortiramo tačke po uglu u odnosu na poziciju pošte. Neka je $dp[l][r]$ najmanja dužina puta, koju poštar mora da pređe, da bi obišao sve planere u intervalu $[l,r]$, ukoliko je to moguće i $inf$ u suprotnom. Neka smo povezali $l$ sa nekom $m$ takvom da je $l<m<r$, to je $dp[l][r] = min_{l<m<r}(dp[l][m]+dp[m+1][r])$. Druga opcija je da povežemo planetu $l$ sa $r$. Dovoljno je da proverimo da li duž koja ih spaja seče duž između pošte i neke druge planete. To možemo da uradimo u $O(N)$. Ukoliko ne seče, imamo još jednog kandidata za rešenje, pa je onda $dp[l][r]=min(dp[l][r],dist(l,r)+dp[l+1][r-1])$, gde je $dist(l,r)$ rastojanje između planete sa indeksom $l$ i planete sa indeksom $r$. Rezultat je u $dp[1][N]$, a vremenska složenost algoritma je $O(N^3)$. Sada možemo rešenje da uopštimo na slučaj da koordinate $Y_i$ nisu pozitivne. Primetimo da kako god povezali planete, uvek možemo da nacrtamo jednu polupravu iz $(0,0)$, koja ne seče ni jednu putanju. Ovo važi zato što se putanje međusobno ne seku. "Luk" koji pravi jedan obilazak dve planete može da bude sadržan u nekom drugom i da sadrži neki drugi, ali ne mogu da se seku. Sada sortiramo tačke po uglu. Ako pretpostavimo da smo povukli tu polupravu negde između $i$ i $i+1$ planete, možemo da posmatramo niz koji je ciklično pomeren ulevo za $i$ mesta i da ponovimo dinamičko kao u prethodnom delu. Ovo rešenje radi u složenosti $O(N^4)$. Međutim možemo da primetimo da veliki deo tog dinamičkog mi izračunavamo više puta. Možemo da dupliramo sortirani niz, tj. ciklično ga ponovimo drugi put i ponovo izračunamo $dp[l][r]$. Primetimo da je sada u $dp[i][i+N]$ upravo rešenje koje se dobija kada bi poluprava bila između planeta $i-1$ i $i$. Pa je krajnji rezultat $min_{1 \leq i \leq N}(dp[i][i+N])$. Vremenska složenost $O(N^3)$, memorijska složenost $O(N^2)$.