Distante intre doua puncte

[•toni2007]

Cum s-ar face optim (mai putin de n^2 log n) urmatoarea problema ?

Deci...

Am n puncte in plan, la care se cunosc coordonatele x[ i ] si y[ i ], si se mai cunoaste m[ i ]. Pentru fiecare punct i imi trebuie sa aflu cele mai apropiate m[ i ] puncte de punctul i, si sa afisez si distanta intre ele. Distanta intre a si b este

min( | x[ a ] - x[ b ] | , | y[ a ] - y[ b ] | ) +1

[•wefgef]

Problema asta e compusa de tine?

Pai mai bine de N^2 e clar ca nu se poate, nu? Daca m[ i ] = N, oricare ar fi i, trebuie sa afisezi N^2 numere. Poti obtine aceasta complexitate cu radix sort cel mai simplu .

[•toni2007]

nu. am gasit-o data la rusi la un concurs... in arhiva de probleme a lui mugurel andreica si erau 10000 de puncte si timpul 2 secunde, deci teoretic nu prea merge n^2. oricum nimeni nu a facut problema in concurs

https://mail.cs.pub.ro/~mugurel.andreica/task_archive/Russia%20-%20Olympiads/CBOSS%20Cup%20(Russia)%20Contests/CBOSS%20Cup%202004-2005/CBOSS%20Cup%20-%20Volga%20Grand%20Prix%20-%20Rusia%202004/results.htm

[•wefgef]

Ar trebuie sa intre N^2... nu e asa mult pentru N = 10.000. Oricum, nu se poate mai bine .

Poate ca rezolvarea oficiala e un smen care optimizeaza mult... cine stie?

[•DITzoneC]

Iti trebuie toate cele m[ i ] puncte sau doar al m[ i ]-lea ?

Daca iti trebuie doar al m[ i ]-lea poti sa il determini cu statistici de ordine. Este tot O(n²), dar cred ca merge mai repede decat sortare cu radix.

[•gabitzish1]

Pentru fiecare punct i imi trebuie sa aflu cele mai apropiate m[ i ] puncte de punctul i, si sa afisez si distanta intre ele.

De aici eu inteleg ca trebuie toate cele m[ i ] puncte.

[•toni2007]

imi trebuie toate cele m [ i ] puncte

https://mail.cs.pub.ro/~mugurel.andreica/task_archive/Russia%20-%20Olympiads/CBOSS%20Cup%20(Russia)%20Contests/CBOSS%20Cup%202004-2005/CBOSS%20Cup%20-%20Volga%20Grand%20Prix%20-%20Rusia%202004/all.pdf

e aici problema, e a 4-a (D,road to home)


Ma rog, nu imi trebuie sa afisez distanta minima intre cele mai apropiate m[ i ] puncte ci ca se salvez intr-o matrice alocata dinamic pt a afla apoi drumul optim... dar e cam acelasi lucru

si cum se poate in n^2?

iese pt fiecare i  m[ i ] operatii? daca e asa atunci se obtine o( Mmax) unde Mmax este numarul muchiilor, si este mai mic decat 4 milioane deci e ok


deci se poate face in m[ i ] pt fiecare i?