pramod wrote: > Karas: Can you please explain your code?
I'll try. If you walk around the circle, you'll hit chord endpoints. The first time you hit an endpoint, we'll call the chord "started". The second time you hit an endpoint, we'll call the chord finished. Lets define "intersect" as "intersect in the interior of the circle", so that intersections on the perimeter don't count. Suppose chord A starts before chord B. They intersect iff chord A finishes after chord B starts, but before chord B finishes. In SL2, Karas keeps track of the finish point of chords which have started, but not yet finished. These are candidate "A" chords. When a new chord starts, it is a "B" chord. He sees how many of the candidate A chords actually intersect B. (How many of the A endpoints are before the B endpoint). His "tot" keeps track of how many times each chord was involved in an intersection as B. > By the way, this problem was supposed to use Balanced Binary Search > Tree. Any ideas? For SL2, Karas needs a structure that supports insert, find, and distance, all in O(lg n) time. A balanced binary tree solution seems appropriate. His "list" can't be just a simple list (O(n) search and distance) or array (O(n) insert). > More over I think your algos are also finding which pairs intersect. > Remember that in the worst case of all chords being diameters, every > pair intersects to the answer is n(n-1)/2 which is O(n^2). How can you > find all the O(n^2) intersections in O(n log(n) time? Because he counts by more than one at a time. (For diameters, he counts 0+1+2+3+...+N-1) For four diameters, A,B,C,D, already sorted into SL1: tot = 0 put A into SL2, tot = 0 B finishes after A, tot = 1, put B into SL2 C finishes after B, tot = 3, put C into SL2 D finishes after C, tot = 6, put D into SL2 remove A from SL2 remove B from SL2 remove C from SL2 remove D from SL2 > The question does not ask to find all the pairs but just to "count" > them. Enumerating the pairs would clearly take O(N^2) time. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
