PointLifeGame | Topcoder Archive

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

{0,0,10,10}

{0,10,0,10}

Returns: "0005.0097 0007.5000"

Same as before, but now there are 10 rounds.

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

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

Returns: "0009.0009 0005.0000"

{3,3,8,0}

{2,1,1,3}

Returns: "0002.4658 0002.1875"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.