pramod wrote: ... > Karas: Can you please explain your code? I sort the chord endpoints based the angle of the radius it terminates from some origin. For each chord, I call the endpoint that comes first in the ordering the "starting" endpoint, and the other one the "ending" endpoint. (I believe the original problem statement said to ignore cases where all endpoints are not unique, so I do this.) If the starting point of chord A comes before the starting point of chord B, A and B intersect if the ending point of A is after the starting point of B AND the ending point of B is after the ending point of A. The strategy is to get the number of intersection by adding up for each chord A, the number of chords intersection it whose starting points come after the starting point of A. In this way each intersection is counted exactly once.
At each endpoint P on the circle, let Cp be the number of chords whose starting endpoint comes before P but whose ending endpoint comes after P. If S and E are the starting and ending endpoints of a chord, then Ce - Cs gives the number of instersecting chords whose starting endpoint is between S and E. So if I add up Ce - Cs for each chord, I get the number of intersections. But the same result can be gotten by accumulating over each endpoint P, subtracting Cp if P is a starting endpoint, and adding Cp if P is an ending endpoint. Sorry, this must be very difficult to understand without diagrams. > By the way, this problem was supposed to use Balanced Binary Search > Tree. Any ideas? Change the vector of endpoints to a map of endpoints (maps are implemented as BBSTs). But my guess is that it would be faster using a vector. ... --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
