|
Titlul: distanta maxima intre 2 puncte in spatiu Scris de: Mihai Leonte din Martie 23, 2006, 19:52:16 Descrierea problemei e simpla: N puncte in spatiu, se cere cea mai mare distanta euclidiana/Manhattan dintre ele. Nu va faceti probleme pentru memorie sau neaparat timp. Ma intereseaza algoritmi cat mai rapizi, si, pe cat posibil, nu chiar SF. Sau, ma rog, orice e bun.
Versiunea in plan se poate rezolva cu "rotating calipers" in O(n), odata ce ai determinat infasuratoarea convexa a punctelor, cel putin asta pentru distante euclidiene. Pentru distante Manhattan, nu stiu un algoritm, dar presupun ca e asemanator ca si pentru 3 dimensiuni. Oricum, am mai vazut problema asta, versiunea Manhattan, pe undeva (daca nu ma insel, poate chiar .campion sau Moisil, dar nu bag mana in foc), si am o sursa-solutie oficiala, dar nu inteleg algoritmul din spatele ei. Mai ales ca face si tot felul de operatii de biti, care daca nu stii exact ce rol au, cam greu sa te prinzi singur. Deci... stie cineva cum se face? Titlul: distanta maxima intre 2 puncte in spatiu Scris de: Adrian Vladu din Martie 23, 2006, 20:11:18 Pentru distanta Manhattan, ideea este foarte diferita de cea pentru distanta euclidiana.
Considera planul 2D si punctele de coordonate xi, yi. Distanta Manhattan intre doua puncte x1, y1 si x2, y2 este |x1 - x2| + |y1 - y2| Expliciteaza modulul si gaseste o rezolvare in 2^D, pentru D = numarul de dimensiuni. :P Titlul: distanta maxima intre 2 puncte in spatiu Scris de: cristi8 din Martie 24, 2006, 18:16:17 problema cu distanta manhattan a fost pe .campion, si din cate stiu era explicat algoritmul la "Descriere solutie"
Titlul: Raspuns: distanta maxima intre 2 puncte in spatiu Scris de: Mihai Leonte din Aprilie 04, 2006, 11:52:02 Considera planul 2D si punctele de coordonate xi, yi. Distanta Manhattan intre doua puncte x1, y1 si x2, y2 este |x1 - x2| + |y1 - y2| Expliciteaza modulul si gaseste o rezolvare in 2^D, pentru D = numarul de dimensiuni. :P Mda. Stiu si eu formula pentru distanta Manhattan intre 2 puncte. Si e aberant ca algoritmul sa fie 2^D, unde D={2,3} in majoritatea cazurilor. Daca iei la rand fiecare 2 puncte, pentru 1000 sau mai mult de puncte ce faci? Ca altfel nu inteleg ce vre isa zici. Titlul: Raspuns: distanta maxima intre 2 puncte in spatiu Scris de: Adrian Vladu din Aprilie 04, 2006, 13:41:26 fie...mai exact e O(N*D + 2^D), unde D e numarul de dimensiuni iar N e numarul de puncte. gandeste un pic inainte
Titlul: Raspuns: distanta maxima intre 2 puncte in spatiu Scris de: Cosmin Negruseri din Aprilie 04, 2006, 13:47:24 Cica mai exact :rotfl:, corect eventual.
|