Problem Statement

A robot needs to climb a flat vertical wall with several handholds on it.

The robot has four mechanial "hands". Each hand can grab a handhold positioned anywhere within or on the boundary of a circle of radius armLength from robot's center. While the robot is climbing the wall, three of the hands have to remain anchored at three distinct handholds at all times. To move between holding positions, the robot can use the fourth hand to grab next handhold and release one of the previous handholds. At the start of the climb the robot can stand on one of its hands anywhere on the ground. Thus, it can grab any single handhold which is not higher than 2*armLength from the ground, and to start climbing it must grab three handholds while still standing on the fourth hand.

The wall is described as a plane with a cartesian coordinate system on it. The ground is the line y = 0. Handhold i is positioned at the point (holdx[i], holdy[i]).

Return the y-coordinate of the highest point the robot can reach with a hand while standing on the ground or hanging on the wall using the other three hands.

Definition

 Class: WallClimbing Method: maxHeight Parameters: int[], int[], int Returns: double Method signature: double maxHeight(int[] holdx, int[] holdy, int armLength) (be sure your method is public)

Notes

-The robot can't grab one handhold with two or more hands.
-The returned value must have an absolute or relative error less than 1e-9.

Constraints

-holdx will contain between 1 and 16 elements, inclusive.
-holdy will contain the same number of elements as holdx.
-Each element of holdx and holdy will be between 1 and 1000, inclusive.
-The location of each handhold will be distinct.
-handLength will be between 1 and 100, inclusive.

Examples

0)

 `{10, 10, 10}` `{20, 40, 60}` `30`
`Returns: 80.0`
 The three handholds are arranged in a vertical line, and it is possible to hang on them and reach 80.0.
1)

 `{20, 40, 60, 80}` `{20, 20, 20, 20}` `20`
`Returns: 40.0`
 The four handholds are arranged in a horizontal line. It is possible to hang on any three successive handholds, but this doesn't let the robot reach higher than from the ground.
2)

 `{10, 10, 10, 10, 10, 10, 10, 10, 10}` `{20, 40, 60, 80, 100, 120, 140, 160, 180}` `30`
`Returns: 200.0`
 Each triple of successive handholds is a valid holding position, and it is possible to get to the triple {6,7,8} and reach a height of 200.
3)

 `{10, 10}` `{10, 20}` `40`
`Returns: 80.0`
 There are not enough handholds to hang on them.
4)

 ```{ 50, 100, 150, 200, 50, 100, 150, 200, 50, 100, 150, 200, 50, 100, 150, 200}``` ```{ 50, 50, 50, 50, 100, 100, 100, 100, 150, 150, 150, 150, 200, 200, 200, 200}``` `25`
`Returns: 50.0`
 Here no three handholds are close enough together for the robot to hang from them.
5)

 ```{ 50, 100, 150, 200, 50, 100, 150, 200, 50, 100, 150, 200, 50, 100, 150, 200}``` ```{ 50, 50, 50, 50, 100, 100, 100, 100, 150, 150, 150, 150, 200, 200, 200, 200}``` `50`
`Returns: 250.0`
 The robot can move to the highest row and hang on a horizontal triple.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13935&pm=7832

Nickolas

Testers:

Rustyoldman , timmac , StevieT , vexorian

Problem categories:

Geometry, Graph Theory