Hi, I came across the following question a couple of days back -
"There are n women sitting at positions (0, 1), (0, 2), . . . , (0, n) in the plane, and there are n men sitting at positions (1, 1), (1, 2), . . . , (1, n). Each woman is interested in communicating with only a subset of the men, and this is described by straight line segments between the women and men. For example, if the woman at (0, 2) is interested only in conversing with the men at (1, 5) and (1, 10), then there are two line segments - one connecting (0, 2) to (1, 5), and the other connecting (0, 2) to (1, 10). Give an O((n^2) log n)-time algorithm to compute the number of communicating pairs that intersect." This essentially requires one to find number of intersection points between line segments in the plane. Any ideas about how to solve this would be appreciated. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
