@Piyush: Initially for partitioning the given circles into the 2 queues u r having an O(n^2) loop, so u are comparing each circle with every other. Now, it is possible that u have 3 or more circles A,B,C intersecting if i got ur algo correct, ur intersection queue will have AB, BC, CA. So, according to the geometry, u will find the areas. But this area would be different than the actual area for intersection of A,B,C.
On Jul 20, 3:48 pm, Piyush Sinha <[email protected]> wrote: > I would like to redefine my algo with cases clarified... > > Create a queue that is made to contain the points... > > say points queue [1000]; > > for i:1 to n > for j:i+1 to n > Calculate d (distance between the two centers) > if (d >= r0 + r1) keep them in two separate queues //the circles > don't intersect > if(d==0 || d<= abs(r0-r1)) > ignore the circle with smaller radius // one circle > wholly contains another such that the borders do not overlap, or > overlap exactly (e.g. two identical circles) > else > keep both of them in one single queue > > Now calculate the area of the circles in those queues which have > single element... > > those with more than one element..calculate the area using simple > geometry...You can take help of > this..http://mathworld.wolfram.com/Circle-CircleIntersection.html > > Hope its clear now... > > On 7/20/11, SAMMM <[email protected]> wrote: > > > > > > > > > > > I doubth . > > > For (d< r0 + r1) ignore the point with smaller radius as it will > > overshadowed the bigger circle completely > > > There may be a case where the circle is partially overlapped by the > > other circles. Then this algo will fail . > > > The area will be of like these :- > > > Suppose 3 circles are there X,Y&Z . > > Then the area will be :- > > > Case1:- X+Y+Z > > Case2:- X+(YUZ) ==>> Y + Z - (YnZ) <--- intersection > > case3:- There circle can overlap ... like these . > > > Then Will your algo work .. I guess no . > > > -- > > 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?hl=en. > > -- > *Piyush Sinha* > *IIIT, Allahabad* > *+91-7483122727* > * <https://www.facebook.com/profile.php?id=100000655377926> "NEVER SAY > NEVER" > * -- 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?hl=en.
