Dogru parcalarinin kesisimleri

Question

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?

Comments

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.