Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Par algoritama za rijesavanje problema analiticke geometrije

[es] :: Art of Programming :: Par algoritama za rijesavanje problema analiticke geometrije

[ Pregleda: 2166 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

2paca.zwaka
Nikola Ninkovic
Web Developer
BTGPort
Trebinje, RS/BiH

Član broj: 277023
Poruke: 126
*.teol.net.



+7 Profil

icon Par algoritama za rijesavanje problema analiticke geometrije21.04.2013. u 23:24 - pre 133 meseci
Moze li neko da mi kaze postoje li vec neki algoritmi za sledece probleme (kao i njima slicne), ako ne, na koji nacin bi tome prisli ?

p1 : dato je n tacaka u ravni, odrediti konveksni mnogougao koji obuhvata sve tacke.
p2 : dato je n tacaka u ravni od kojih su neke plave a neke crvene, odrediti broj trouglova sa tjemenima u crvenim tackama koji ne sadrze ni jednu plavu tacku.

oba problema trebaju da imaju sto manju slozenost, tj. da se izvrsavaju sto je brze moguce (<1s) tako da brute-force algoritmi ne dolaze u obzir.

hvala
while(I->AmAlive()){
I->DoSomeProgramming();
}
 
Odgovor na temu

chaami
Goran Petrović
nezaposlen
Beograd

Član broj: 262685
Poruke: 84
*.mediaworksit.net.



+28 Profil

icon Re: Par algoritama za rijesavanje problema analiticke geometrije22.04.2013. u 18:22 - pre 133 meseci
Ima više algoritama koji rešavaju konveksni omotač. Tebi bi možda najviše odgovarao grahamov algoritam (za prvi problem). Složenost mu je O(n log n).
 
Odgovor na temu

Picsel
Beograd

Član broj: 39817
Poruke: 440
*.dynamic.isp.telekom.rs.



+7 Profil

icon Re: Par algoritama za rijesavanje problema analiticke geometrije24.04.2013. u 12:36 - pre 133 meseci
Sto se problema 2 tice:

Za svaku duz cija su temena crvene boje, povuku se vertikalne poluprave iz oba temena duzi na dole. Zatim se za oblast koja je odozgo ogranicena sa tom duzi, s leve strane sa levom polupravom, s desne strane s desnom polupravom i sa -beskonacno odozdo prebroji koliko plavih tacaka se nalazi u njoj. To zapises u nekoj matrici.
Ovaj deo algoritma je O(N^2 * M), gde je N broj crvenih tacaka (ima O(N^2) duzi, tj. oblasti), a M broj plavih tacaka.

Zatim se za svaki trougao cija su temena crvene boje, u O(1) proverava koliko plavih tacaka se nalazi u tom trouglu principom ukljucenja i iskljucenja. Odnosno, kad se fiksira jedan trougao, na osnovu ranije izracunatih oblasti ti mozes da izracunas koliko tacno plavih tacaka se nalazi u trouglu i proveris da li je taj broj jednak nuli. Ovaj deo algoritma je O(N^3).
Ukupna slozenost je O(N^2*(N + M)).
 
Odgovor na temu

[es] :: Art of Programming :: Par algoritama za rijesavanje problema analiticke geometrije

[ Pregleda: 2166 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.