Topic

z-skakac

nrmmyth1970-01-01 04:26:32

Zanimaju me vasa rijesenja.
I kad ce biti dostupni test podatci za ovaj problem.

Pozdrav.

rajkon1970-01-01 11:11:13

Moje reshenje :

od svake krajnje tacke linije sam napravio novih 8 tacaka (+-0.01,+-0.01) ...
i onda povezem one koje mogu da se povezu, pustim bfs, i to je to ... :)

nrmmyth1970-01-01 14:35:47

nesto sam i ja slicno napravio... slijedi da je greska bila u kodu ne u algoritmu...

nalism2006-11-19 09:26:41

jel postoji laksi i brzi nacin proveravanja da li se dve duzi seku, osim racunanja presecne tacke ?? sta mislite?

andrejko2006-11-19 10:13:52

Pa jednostavno je. Da bi ispitao da li se duzi AB i CD seku samo treba da vidis daje VP (A, B, C) * VP (A, B, D) <= 0 i VP (C, D, A) * VP (C, D, B) <= 0. To ustvari znaci da su tacke C i D sa razlicitih strana prave AB (tj. da cu A i D sa razlicitih strana prave CD).

nalism2006-11-19 10:36:44

sta je "VP"? :)

renovator2006-11-19 10:46:10

vektorski proizvod

nalism2006-11-19 11:04:11

cek, cek, onda ne razumem oznaku VP (tacka A, tacka B, tacka C)? ???
jel to vektorski proizvod vektora AB i vektora BC!

andrejko2006-11-19 11:29:52

Izvinjavam se sto to nisam objasnio :-)
Da VP (A, B, C) je proizvod vektora AB i BC, tj.


VP (A, B, C) = (A.x - B.x) * (C.y - B.y) - (C.x - B.x) * (A.y - B.y)

tj.
Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â | 1Â  A.xÂ  A.y |
VP (A, B, C) = | 1Â  B.xÂ  B.y |
Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â | 1Â  C.xÂ  C.y |

Takodje imas da je: |VP (A, B, C)| * 0.5 = Povrsina_trougla_ABC.

nalism2006-11-19 11:40:24

da, da... sad je jasno, provalio sam! :)
jos sam pomislio da se onda vektorski mora racunati uz pomoc sinusa a ovako je preko determinante jos lakse!
hvala puno Andrejko!