|
Titlul: Envelope Scris de: Popescu Silviu din Iunie 08, 2011, 22:39:00 Salut, stie cineva unde gasesc informatii despre algoritmul de Envelope ? ( Upper-Envelope , Lower-Envelope ) Tocmai am dat peste termen si mi se pare interesant :D
Titlul: Răspuns: Envelope Scris de: Oancea Catalin din Iunie 09, 2011, 08:18:28 Te referi la "Upper Envelope of Segments"?
Titlul: Răspuns: Envelope Scris de: Gabriel Bitis din Iunie 09, 2011, 08:57:56 Cauta sa vezi daca gasesti descrierea solutiei la problema Forum de la runda 1 .campion 2009.
Titlul: Răspuns: Envelope Scris de: Popescu Silviu din Iunie 09, 2011, 09:52:05 Ma refer la Envelope in general :D.
Poi de la problema aia am aflat de asta si m-a lasat rece ](*,) ca nu explica cum se face envelope :D Titlul: Răspuns: Envelope Scris de: MciprianM din Iunie 09, 2011, 14:09:43 Dupa o cautare pe google am gasit destul de multe rezultate. Gandeste-te la o multime de curbe(marcate intr-un sistem de coordonate) si ca aceste curbe reprezinta niste ziduri inalte dupa care nu poti vedea nimic. Apoi gandeste-te ca te plimbi pe axa Ox de la minus infinit la plus infinit si te uiti pe o directie paralela cu Oy, sensul inspre y. Toate punctele pe care le vezi formeaza lower envelope. Pentru upper envelope, faci ceva similar pe o dreapta paralela cu oX, aflata undeva la infinit, doar ca de data asta te uiti in jos.
Putin formal lower envelope L = { (x,y)|x in R && (x,y) e pe o curba din cele date si y minim } Edit: Si un link: http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Envelope_2/Chapter_main.html (http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Envelope_2/Chapter_main.html) Titlul: Răspuns: Envelope Scris de: Popescu Silviu din Iunie 09, 2011, 22:23:14 Aaa :D am inteles.
Da tot nu stiu cum s-o fac in O(1) adica, sti vre-un site sa spuna cum se foloseste? Titlul: Răspuns: Envelope Scris de: Cezar Mocan din Iunie 12, 2011, 16:36:29 Problema Forum se poate rezolva si cu Diagrame Voronoi (trebuie sa gasesti celula Voronoi a punctului (0, 0) si apoi pentru fiecare query sa verifici daca punctul se afla in celula). Am prezentat asta la lot, daca vrei mai multe detalii / sursa spune.
Titlul: Răspuns: Envelope Scris de: Popescu Silviu din Iunie 13, 2011, 13:30:17 Poti sa clarifici , pls ?
Cum gasesti elementele dominante ( ca in problema terenuri :D ) ale punctului (0,0) ? Titlul: Răspuns: Envelope Scris de: Cezar Mocan din Iunie 13, 2011, 14:18:32 Citeste putin aici (http://infoarena.ro/voronoi), explica bine principiul dualitatii si diagramele Voronoi. Pe scurt, celula Voronoi a punctului (0, 0) reprezinta locul geometric al punctelor care sunt mai apropiate de el decat de celelalte N puncte, si are forma unui poligon convex (posibil deschis). Se poate determina in O(N log N) folosind dualizarea si o infasuratoare convexa. Sper sa iti fie de folos, daca mai ai intrebari nu ezita sa le pui!
|