Thursday, August 5, 2010

Maximum number of rings



There are a number of rings lying on the floor.
Any two rings can intersect at two points, may not intersect at all, or touch
each other at a single point. Two rings can be lifted simultaneously if and only
if they intersect at two points. A bunch of rings mutually satisfying this
condition can be lifted at once. You have to find the maximum number of rings
that can be lifted in a single attempt. The rings are specified by their x and y coordinates on the floor and their radius, the specifications of a ring being in a single row of a matrix.



        static void Main(string[]
args)



        {          



            int
maxcount = 1;



            double[,]
arr ={



                               {0.0, 0.0, 1.0},



                               {1.0, 0.0, 1.0},



                               {2.0, 0.0, 1.0},



                               {-1.0, 0.0, 1.0}



                           };



            int
num = arr.GetLength(0);



            //Array
to keep track of the rings included in the present bunch.



            int[]
used = new int[num];



            for
(int i = 0; i < arr.GetLength(0); i++)//Denotes the starting ring.



            {



                int
thiscount = 1;



                for
(int m = 0; m < num; m++)



                {



                    used[m] = 0;



                }



                used[i] = 1;//Starting ring has been used.



                //Searching
a ring from the beginning which matches the conditions.



                for
(int j = 0; j < arr.GetLength(0); j++)



                {                                               



                    if
(used[j] == 0)



                    {



                        //Searching from the beginning from the beginning of the current bunch.



                        for (int n = 0; n < num; n++)



                        {



                            double dist = Math.Sqrt(Math.Pow((arr[n, 0] - arr[j, 0]), 2.0d) + Math.Pow((arr[n, 1] - arr[j, 1]), 2.0d));



                            if (used[n] == 1 && dist < arr[j, 2] +
arr[n, 2] && dist > Math.Abs(arr[j,
2] - arr[n, 2]))



                            {



                                used[j] = 1;



                                thiscount++;



                                break;



                            }



                        }



                    }



                }



                if
(thiscount > maxcount)



                {



                    maxcount = thiscount;



                }



            }



            Console.WriteLine("The maximum number of rings is: " +
maxcount);



        }

1 comment: