http://www.codechef.com/FEB10/problems/M5/
On Wed, Jul 20, 2011 at 5:35 PM, Piyush Sinha <[email protected]>wrote: > @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 <[email protected]> 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 <[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. >> >> > > > -- > *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 [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. > -- 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.
