Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
324 kez görüntülendi
Elimde $n$ tane dogru parcalasi var. Bu dogru parcalarinin bir ucu kirmizi diger ucu ise mavi olsun.

Ben bu dogru parcalarinin kesisimleri ile ilgileniyorum. Daha da spesifik olarak bir duzlem uzerinde verilen dogru parcalarinin, kirmizi uclarina en yakin kesisim noktalarini ve kesisen dogru parcalarinin adlarini istiyorum. Bunu bulmak icin akliniza gelen en verimli yontem nedir?
Serbest kategorisinde (1.6k puan) tarafından  | 324 kez görüntülendi
Verimini bilmem ama
Bu dogruları (a,b)+t(c,d) olacak şekilde t değeri 0 ile 1 arasında olacak şekilde yazabilirsin.
Kırmızı olanları 1 olacak şekilde dizayn edelim.
Diğer n-1 doğru parçası için keşişim varsa bunları (t değerlerini) bir kümeye alalım.
En büyüğü istenen doğruyu verir.
Bunlar basit hesaplamalar olduğu için pek verimsiz de sayılmaz.

Ya her dogru parcasini diher tum dpgru parcalariyla kesistiriyorujm degil mi? Bu islemi $n^2$ kadar yapmam gerekiyor sanirim. Bundan sora da kesisim zamanlarinii siralamam gerekiyor. Kabaca calisma zamani $O(n^2)$ oldu. sanki $O(n\log n)$ de yapilirmis gibi geliyor bana.

not: su soru  ile ilgili dusunurken cikarttim bu soruyu bu arada

Muhtemelen bu kısım için algoritmalar vardır.
Detaylı bakmadım ama burada "Sweep Line Algorithm" diye bir şey var, nlogn olan.

Tesekkur ederim bu gercekten yararli olacak gibi duruyor.
20,194 soru
21,723 cevap
73,246 yorum
1,848,242 kullanıcı