@Dumanshu..i am not partitioning them into just two queues... Moreover I just gave a raw idea...and yeah the complexity is in the order of n^2 only..... There are many chances of improvement in it..
On Wed, Jul 20, 2011 at 5:30 PM, Dumanshu <duman...@gmail.com> wrote: > @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 <ecstasy.piy...@gmail.com> 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 <somnath.nit...@gmail.com> 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 algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
