[algogeeks] Re: Circle Circle more Circles .........
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,YZ . 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.
Re: [algogeeks] Re: Circle Circle more Circles .........
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,YZ . 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=10655377926 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.
Re: [algogeeks] Re: Circle Circle more Circles .........
@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,YZ . 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=10655377926 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=10655377926 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.
Re: [algogeeks] Re: Circle Circle more Circles .........
http://www.codechef.com/FEB10/problems/M5/ On Wed, Jul 20, 2011 at 5:35 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @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,YZ . 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=10655377926 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* * 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. -- 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.
[algogeeks] Re: Circle Circle more Circles .........
See the input will be :- 6 No of circles x1 y1 R1 x2 y2 R2 x3 y3 R3 x4 y4 R4 x5 y5 R5 x6 y6 R6 Output:- Area occupied by the above circles (one line) 4 decimal points . On Jul 19, 9:01 pm, priyanka goel priya888g...@gmail.com wrote: can u pl tell wat is dis x y coordinate? are dey centre coordinates or any point on circumference of circle.. -- 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.
Re: [algogeeks] Re: Circle Circle more Circles .........
Just a simple thoughtI am assuming all points are unique 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 if(d r0 + r1) ignore the point with smaller radius //as it will overshadowed the bigger circle completely 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... Hope the above algo is clear... On 7/19/11, SAMMM somnath.nit...@gmail.com wrote: See the input will be :- 6 No of circles x1 y1 R1 x2 y2 R2 x3 y3 R3 x4 y4 R4 x5 y5 R5 x6 y6 R6 Output:- Area occupied by the above circles (one line) 4 decimal points . On Jul 19, 9:01 pm, priyanka goel priya888g...@gmail.com wrote: can u pl tell wat is dis x y coordinate? are dey centre coordinates or any point on circumference of circle.. -- 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=10655377926 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.
