[algogeeks] Re: Circle

2011-08-05 Thread Dave 
@Don: The sequence of points (x+a, y+b) generated by your algorithm
moves along the arc of the circle from theta = 90 degrees to theta =
45 degrees. Along this arc, the slope of the curve is -1 <= dy/dx <=
0. Thus, rather than moving from (x+a, y+b) to either (x+a+1, y+b) or
(x+a, y+b-1), you should be moving to either (x+a+1, y+b) or (x+a+1, y
+b-1). In words, you always increase a, and decrease b when that gets
you closer to the circle. Furthermore, you can algebraically simplify
the comparison so that no multiplications are required. See, e.g.,
http://homepage.smc.edu/kennedy_john/bcircle.pdf.

Dave

On Aug 5, 1:06 pm, Don  wrote:
> // Draw a circle with center (x,y) and radius r
> circle(int x, int y, int r)
> {
>   int a = 0;
>   int b = r;
>   while(a <= b)
>   {
>     // Draw the current location in all 4 quadrants
>     plot(x+a, y+b);
>     plot(x-a,  y+b);
>     plot(x+a, y-b);
>     plot(x-a, y-b);
>     plot(x+b, y+a);
>     plot(x-b,  y+a);
>     plot(x+b, y-a);
>     plot(x-b, y-a);
>
>     // Look at two possible next points and pick the better
>     int delta1 = r*r - (a+1)*(a+1) - b*b;
>     int delta2 = r*r - a*a - (b-1)*(b-1);
>     if (delta1*delta1 < delta2*delta2) ++a;
>     else --b;
>   }
>
> }
>
> On Aug 5, 8:38 am, rShetty  wrote:
>
>
>
> > Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without
> > making use of any floating point
> > computations at all.- Hide quoted text -
>
> - Show quoted text -

-- 
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

2011-08-05 Thread Don 
// Draw a circle with center (x,y) and radius r
circle(int x, int y, int r)
{
  int a = 0;
  int b = r;
  while(a <= b)
  {
// Draw the current location in all 4 quadrants
plot(x+a, y+b);
plot(x-a,  y+b);
plot(x+a, y-b);
plot(x-a, y-b);
plot(x+b, y+a);
plot(x-b,  y+a);
plot(x+b, y-a);
plot(x-b, y-a);

// Look at two possible next points and pick the better
int delta1 = r*r - (a+1)*(a+1) - b*b;
int delta2 = r*r - a*a - (b-1)*(b-1);
if (delta1*delta1 < delta2*delta2) ++a;
else --b;
  }
}

On Aug 5, 8:38 am, rShetty  wrote:
> Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without
> making use of any floating point
> computations at all.

-- 
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 .........

2011-07-20 Thread Pankaj 
http://www.codechef.com/FEB10/problems/M5/

On Wed, Jul 20, 2011 at 5:35 PM, Piyush Sinha 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  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  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  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*
>> > *  "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.

Re: [algogeeks] Re: Circle Circle & more Circles .........

2011-07-20 Thread Piyush Sinha 
@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  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  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  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*
> > *  "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.

[algogeeks] Re: Circle Circle & more Circles .........

2011-07-20 Thread Dumanshu 
@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  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  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*
> *  "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 .........

2011-07-20 Thread Piyush Sinha 
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  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*
*  "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.

[algogeeks] Re: Circle Circle & more Circles .........

2011-07-20 Thread SAMMM 
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.

Re: [algogeeks] Re: Circle Circle & more Circles .........

2011-07-19 Thread Saket Choudhary 
^The condition if d < r0+r1 means the circles are intersecting hence theres
no way a bigger circle will overshadow the smaller circle which will happen
only whne d < abs(r1-r0)

On 20 July 2011 00:00, Piyush Sinha  wrote:

> 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  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  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*
> *  "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.

Re: [algogeeks] Re: Circle Circle & more Circles .........

2011-07-19 Thread Piyush Sinha 
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  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  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*
*  "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.

[algogeeks] Re: Circle Circle & more Circles .........

2011-07-19 Thread SAMMM 
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  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.

[algogeeks] Re: Circle Arrangement Problem

2006-12-25 Thread Vector 


I have a solution described in Chinese
http://blog.csdn.net/xlvector/archive/2006/11/14/1384370.aspx

There are code there too


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Circle Arrangement Problem

2006-12-19 Thread Amal 
Only Males remain - Does it mean all the males should remain or the people
remain should be males ?

 If the people remain should be males then it is just josephus problem or it
is an extension to it.

Amal.


On 12/18/06, Darth <[EMAIL PROTECTED]> wrote:
>
>
> thanks everyone for your input. This is the josephus problem.
>
>
> >
>


--~--~-~--~~~---~--~~
 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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Circle Arrangement Problem

2006-12-18 Thread Darth 

thanks everyone for your input. This is the josephus problem.


--~--~-~--~~~---~--~~
 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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Circle Arrangement Problem

2006-12-09 Thread jack wang 

if the positons of females are determined ,the arrangement is done .

we can simulate the removing process. so ,the first female must be
placed at  position  kmod(x+y) ,using mod in case that k is greater
than x+y. then we shrink the length of the list  ,  the similar
situation appears ,only we start at position kmod(x+y-1).  This can be
implemented in a linkedlist with struct of the node keeping a satellite
value of the initial position.


--~--~-~--~~~---~--~~
 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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Circle Arrangement Problem

2006-12-08 Thread Zhen Liang 
ho,sorry for mistaking the meaning of subject.


在06-12-9，Robby <[EMAIL PROTECTED]> 写道：
>
>
> To ZhenLiangSC:
>
> I am afraid not.
>
> If a person is removed, he won't be counted after that.
>
> ps. The best algorithm I can find is O(NlogN), by employing an interval
> tree or something like that.
>
> Sorry for my poor English, too... :)
>
> "[EMAIL PROTECTED] 写道：
> "
> > first put f to the temp=k-th position,than put to the temp=k*2
> > position..
> > when temp=k*n>x+y,make temp=temp-(x+y)
> > until y times
> > right?
> > i am not good at English,sorry.
> >
> > On 12月8日, 下午2时23分, "Darth" <[EMAIL PROTECTED]> wrote:
> > > Hi,
> > >
> > > I think this is a standard problem but can't remember what is the
> exact
> > > name assigned to this problem. Neways, plz help me solve this one.
> > >
> > > The problem is as follows :
> > >
> > > Given X number of males and Y number of females and a number k,
> > > construct an arrangement of the males and females in a circle so that
> > > starting at the first person and removing every person at a distance
> of
> > > k-1 in clockwise direction, Y number of times only males remain in the
> > > circle.
> > >
> > > For e.g. X=5,Y=3,k=2
> > >
> > > "MFMFMFMM"
> > >
> > > The distance between neighbours in the circle(ring) is 1(one).
> > >
> > > TIA,
> > > Darth
>
>
> >
>


-- 
A passion to win and a thirst to succeed.
http://zhenliangsc.blog.phoenixtv.com

--~--~-~--~~~---~--~~
 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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Circle Arrangement Problem

2006-12-08 Thread Robby 

To ZhenLiangSC:

I am afraid not.

If a person is removed, he won't be counted after that.

ps. The best algorithm I can find is O(NlogN), by employing an interval
tree or something like that.

Sorry for my poor English, too... :)

"[EMAIL PROTECTED] 写道：
"
> first put f to the temp=k-th position,than put to the temp=k*2
> position..
> when temp=k*n>x+y,make temp=temp-(x+y)
> until y times
> right?
> i am not good at English,sorry.
>
> On 12月8日, 下午2时23分, "Darth" <[EMAIL PROTECTED]> wrote:
> > Hi,
> >
> > I think this is a standard problem but can't remember what is the exact
> > name assigned to this problem. Neways, plz help me solve this one.
> >
> > The problem is as follows :
> >
> > Given X number of males and Y number of females and a number k,
> > construct an arrangement of the males and females in a circle so that
> > starting at the first person and removing every person at a distance of
> > k-1 in clockwise direction, Y number of times only males remain in the
> > circle.
> >
> > For e.g. X=5,Y=3,k=2
> >
> > "MFMFMFMM"
> >
> > The distance between neighbours in the circle(ring) is 1(one).
> > 
> > TIA,
> > Darth


--~--~-~--~~~---~--~~
 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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Circle Arrangement Problem

2006-12-08 Thread [EMAIL PROTECTED] 

first put f to the temp=k-th position,than put to the temp=k*2
position..
when temp=k*n>x+y,make temp=temp-(x+y)
until y times
right?
i am not good at English,sorry.

On 12月8日, 下午2时23分, "Darth" <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I think this is a standard problem but can't remember what is the exact
> name assigned to this problem. Neways, plz help me solve this one.
>
> The problem is as follows :
>
> Given X number of males and Y number of females and a number k,
> construct an arrangement of the males and females in a circle so that
> starting at the first person and removing every person at a distance of
> k-1 in clockwise direction, Y number of times only males remain in the
> circle.
>
> For e.g. X=5,Y=3,k=2
>
> "MFMFMFMM"
>
> The distance between neighbours in the circle(ring) is 1(one).
> 
> TIA,
> Darth


--~--~-~--~~~---~--~~
 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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Circle Arrangement Problem

2006-12-08 Thread dixiecko 

it looks like extended Josephus election problem.

On Dec 8, 7:23 am, "Darth" <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I think this is a standard problem but can't remember what is the exact
> name assigned to this problem. Neways, plz help me solve this one.
>
> The problem is as follows :
>
> Given X number of males and Y number of females and a number k,
> construct an arrangement of the males and females in a circle so that
> starting at the first person and removing every person at a distance of
> k-1 in clockwise direction, Y number of times only males remain in the
> circle.
>
> For e.g. X=5,Y=3,k=2
>
> "MFMFMFMM"
>
> The distance between neighbours in the circle(ring) is 1(one).
> 
> TIA,
> Darth


--~--~-~--~~~---~--~~
 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 [EMAIL PROTECTED]
For more options, visit this group at 
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---