TopCoder problem "PointLifeGame" used in SRM 221 (Division II Level Two)



Problem Statement

    Given a set S of points in the plane we can generate a new set T in the following fashion:
  • 1) For all distinct points p and q in S, the midpoint of the line segment from p to q should be added to T.
  • 2) Remove all duplicate points in T so that there is only one copy of each point in T.
The process used to convert S into T is called a round.



You will be given int[]s xs and ys denoting the points contained in S. Point i will have x-coordinate xs[i] and y-coordinate ys[i]. After applying rnds rounds to S, you will return the best point. One point is better than another if it has a larger y-coordinate. In case of a tie, the point with the larger x-coordinate is then better. The returned point should have the form (quotes for clarity) "x y" where x and y denote the x and y coordinates respectively. Each coordinate has the format (quotes for clarity) "####.####". In other words, there should be exactly 4 digits before the decimal place and 4 digits afterward. When necessary, round down to the nearest ten-thousandth.
 

Definition

    
Class:PointLifeGame
Method:simulate
Parameters:int[], int[], int
Returns:String
Method signature:String simulate(int[] xs, int[] ys, int rnds)
(be sure your method is public)
    
 

Constraints

-xs must contain between 3 and 50 elements inclusive.
-ys must contain the same number of elements as xs.
-Each element of xs will be between 0 and 5000 inclusive.
-Each element of ys will be between 0 and 5000 inclusive.
-rnds must be between 1 and 10 inclusive.
-Each given point will be distinct.
 

Examples

0)
    
{0,0,10,10}
{0,10,0,10}
1
Returns: "0005.0000 0010.0000"
The given points are arranged in a 10 by 10 square. After 1 round the best point lies on the middle of the top edge of the original square.
1)
    
{0,0,10,10}
{0,10,0,10}
10
Returns: "0005.0097 0007.5000"
Same as before, but now there are 10 rounds.
2)
    
{0,10,20}
{0,10,0}
1
Returns: "0015.0000 0005.0000"
Here we have a triangular arrangement. After 1 round the best point lies on the upper right edge of the original triangle.
3)
    
{1,2,3,4,5,6,7,8,9,10, 
 1,2,3,4,5,6,7,8,9,10, 
 1,2,3,4,5,6,7,8,9,10, 
 1,2,3,4,5,6,7,8,9,10, 
 1,2,3,4,5,6,7,8,9,10}
{1,1,1,1,1,1,1,1,1,1, 
 2,2,2,2,2,2,2,2,2,2,
 3,3,3,3,3,3,3,3,3,3,
 4,4,4,4,4,4,4,4,4,4,
 5,5,5,5,5,5,5,5,5,5}
10
Returns: "0009.0009 0005.0000"
4)
    
{3,3,8,0}
{2,1,1,3}
10
Returns: "0002.4658 0002.1875"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3447

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5867&pm=3447

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom

Problem categories:

Simulation, Sorting