1 ) Radially sort the all the points of each chord (start and end both ).
2 ) Start with the first start point. Have c=1, tot=0, done[1..n]=0
3 ) Till all points are done:
a ) If its a start point then
tot = tot + c
c = c + 1
set done for this point 1
else if it is an end point of a start point processed then
c = c- 1;
set done for this point 1
4 ) Answer is tot.
-Dhyanesh
On 4/20/06, pramod <[EMAIL PROTECTED]> wrote:
>
> There are 'n' chords of a circle. How to find the number of pairs of
> the chords which are intersecting in O(n log(n)) time. All the end
> points of the chords are unique.
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
