[ 2paca.zwaka @ 21.04.2013. 23:24 ] @
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
[ chaami @ 22.04.2013. 18:22 ] @
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).
[ Picsel @ 24.04.2013. 12:36 ] @
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)).