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)~.