TopCoder problem "FallingPoints" used in SRM 431 (Division II Level Two)



Problem Statement

    You are given a int[] X containing the x-coordinates of several points. Each point starts at an infinitely high y-coordinate. Starting with the first point, each point falls down until it is either a distance of R away from a previously fallen point or it reaches y = 0. Each point (after the first point) will start falling only when the previous one stops. Return a double[], where the i-th element is the final y-coordinate of the i-th point.
 

Definition

    
Class:FallingPoints
Method:getHeights
Parameters:int[], int
Returns:double[]
Method signature:double[] getHeights(int[] X, int R)
(be sure your method is public)
    
 

Notes

-Each element of your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-X will contain between 1 and 50 elements, inclusive.

-All elements of X will be between 0 and 1,000, inclusive.

-R will be between 1 and 1,000, inclusive.

 

Examples

0)
    
{0}
10
Returns: {0.0 }
There is only one point and it will just fall down.
1)
    
{1,100}
10
Returns: {0.0, 0.0 }
Both points will fall down.
2)
    
{0,9}
10
Returns: {0.0, 4.358898943540674 }
The first point falls down. The second point stops at a distance of 10 away from the first point.
3)
    
{0,9,19}
10
Returns: {0.0, 4.358898943540674, 4.358898943540674 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13522&pm=10261

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Simple Math