Treba vam objasnjenje nekog algoritma? Ili imate zelju da pokazete znanje iz ove oblasti? Ovo je pravo mjesto za to..

PS: Tema nije vezana za konkretan programski jezik, tako da je najbolje rjesenja pisati u pseudo kodu.

Naisao sam na zanimljiv zadatak, a nikako ne mogu da smislim algoritam za njegovo rjesavanje.
Dakle... Ako je u ravni dato n duzi (n < 1000), sa koordinatama njihovih tacaka, treba odrediti koliko se najvise duzi moze presjeci jednom pravom.

P.S. Odgovara mi i matematicko rjesenje!

koliko sam ja skontao to bi moglo da bude ovako...nisam siguran ali pokusacu,zasad samo matematicki a kad budem imao vremena i napisati ga u c++...
ako duz(AB) definisemo sa cetiri tacke,A(a,b) i B(c,d) po nekoj mojoj logici,prava koja bi sjekla te duzi bi prolazila kroz one duzi koje imaju najvise zajednickih tacaka,tj.NPR.ako od 10 duzi,njih 6 ima zajednicku tacku (a) u kordinatnom sistemu,prava ce prolaziti kroz sve te tacke i ujedno ta prava ce sjeci najvise duzi,tj 6 duzi...
to bi se moglo fino uraditi sa nizovima,tako da ci budem imao malo vremena ,pogledacu malo ovo i napisati nesto u c++...
zasad toliko...mozda neko drugi ima neko drugo matematicko rjesenje koje je tacno....(ovo je po nekoj mojoj logici,ako neko zna tacno matematicko rjesenje nek napise,to bi dosta pomoglo)

hm.. nisam siguran da je tvoje rjesenje u redu,,

Citat:

ako od 10 duzi,njih 6 ima zajednicku tacku (a) u kordinatnom sistemu,prava ce prolaziti kroz sve te tacke i ujedno ta prava ce sjeci najvise duzi,tj 6 duzi...

Da li ovdje mislis da se tih 6 duzi medjusobno sijeku u jednoj tacki, ili da kad se projektuju na ose koordinatnog sistema imaju presjek u jednoj tacki? U svakom slucaju ovo nije ok, jer prava moze da sjece sve duzi iako se one medjusobno ne sijeku..

Zadatak je prilicno komplikovan, trenutno mi na pamet pada samo brute force rjesenje, ali bi i ono bilo izuzetno neefikasno, a nimalo elegantno.. Sedgewick u svojoj knjizi Algoritmi rjesava slican problem, odredjuje koliko se duzi u koordinatnom sistemu medjusobno sijeku, medjutim ovo uvodjenje prave zadatak dodatno komplikuje.

Razmislicu i proguglacu malo o problemu, pa ako nadjem adekvatno rjesenje, postovacu ga ovdje.

_________________
Linux registered user #449109

to bi mogao da bude jedan od uslova ispitivanja...

ne ,ne mislim da se tih 6 duzi sjeku u istoj tacki,nego ako duz ima zajednicku tacku (a),ne mora znaciti da ce se ta duz sjeci sa nekom drugom duzi koja ima istu tacku (a) jer im je razlicita kordinata (b) ..npr duz(1.3)(5.2) i duz(1.4)(8,6) ,ima jednaku kordinat (a) ali
one se ne dodiruju ni u jednoj tacki.....
nisam siguran da li ovaj uslov moze uradi ono sto se trazi,ovo sam cisto iz nekog crteza zakljucio,ako neko zna matematicko rjesenje,bice onda lakse

cek, ti si govorio o provjeri da li se dve (ili vise) duzi sijeku? To nije problem, na http://www.elitesecurity.org/t171876-0#1118541 sam stavio kod koji odredjuje upravo to. Medjutim sama ta f-ja nam nece mnogo pomoci..

Zaboravio sam da dodam da su koordinate tacaka realni brojevi. Ako bi te koordinate bile cjelobrojnog tipa, onda je zadatak prilicno jednostavan.
Brute force rjesenje je moguce ako bi se date koordinate prosirile, tako da se od njih dobiju cijeli brojevi, pa se onda takvi brojevi prebace u dvodimenzionu matricu i pretraze sva rjesenja; ali ovo je krajnje neefikasno jer uzima i memoriju i vrijeme.

ajd prvo napisi zadatak ako su brojevi cjelobrojnog tipa,ili matematicko rjesenje napisi kad je takojednostavno,pa cemo onda pokusavati sa realnim brojevima...

Pa, ja sam rekao da je to brute force rjesenje, i da je neefikasno. Mada se zadatak moze rijesiti i sa realnim brojevima tako da se provjerava da li odredjeni broj duzi moze biti presjecen istom pravom, pa primijeniti tu funkciju na sve grupe duzi.
Funkcija za provjeru grupe duzi bi radila tako sto iz niza a[n], koji sadrzi pocetne tacke svih duzi (gledano po x-osi), nadje najveci elemenat t1, a iz niza b[n], koji sadrzi krajnje tacke svih duzi (po x-osi), nadje najmanji elemenat t2; pa onda oduzme t2-t1, i ukoliko je rezultat pozitivan data grupa duzi moze biti presjecena jednom pravom.
Ovo se lako dokazuje. Ali i na ovaj nacin rjesavanje bi trajalo dugo... Sto se tice matematickog rjesenja... nisam siguran da se ovaj zadatak moze rijesiti samo matematicki.