infoarena > infoarena - concursuri, probleme, evaluator, articole > Articole > Subiect: Minimal enclosing circle
Pagini: [1]   În jos
« mesajul precedent următorul mesaj »
  Imprimă  
Ajutor Subiect: Minimal enclosing circle  (Citit de 3114 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
•wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« : Noiembrie 18, 2007, 16:14:46 »
Un prieten de-ai mei mi-a spus recent o problema care are legatura cu articolul prezentat.

Dandu-se N puncte in plan, sa se demonstreze ca daca enclosing circle-ul pentru oricare 3 puncte are raza <= 1, atunci enclosing circle-ul pentru toate cele N puncte are raza <= 1.

Demonstrand cele afirmate mai sus, putem gasi o noua metoda brute-force in O(N^3). Pur si simplu luam oricare 3 puncte, calculam raza enclosing cicle-ului si retinem maximul dintre razele astea.
« Ultima modificare: Noiembrie 18, 2007, 16:16:52 de către Andrei Grigorean » Memorat
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
•Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #1 : Noiembrie 18, 2007, 16:26:12 »
Stai, daca ai 3 puncte colineare, raza celui mai mic cerc e infinit, dar tu ai un cerc ce el contine de diametru egal cu distanta intre cele mai departate doua. Ce nu inteleg?

Edit:mda, tu ziceai de enclosing circle nu cerc circumscris ...

O varianta mai inceata, dar mai rapida ca n^4 ar fi sa faci cautare binara pe dimensiunea razei.
« Ultima modificare: Noiembrie 18, 2007, 16:40:37 de către Cosmin Negruseri » Memorat
•wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #2 : Decembrie 14, 2007, 14:48:25 »
Nu incearca nimeni sa rezolve problema prezentata? Sad
Memorat
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
•stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« Răspunde #3 : Februarie 20, 2009, 02:14:04 »
Discutiile pot continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3684.0
Memorat
Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
Pagini: [1]   În sus
  Imprimă  
infoarena > infoarena - concursuri, probleme, evaluator, articole > Articole > Subiect: Minimal enclosing circle
 « mesajul precedent următorul mesaj »
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines