TopCoder Statistics - Problem Statement

Problem Statement

A piecewise-linear directed path in the plane is defined by a sequence of points (its vertices). It is said to be "ccw-turning" if at each vertex (other than the first and last) as the path is traversed the heading changes by more than 0 but less than 180 degrees counterclockwise. The path may intersect itself or even trace over itself.

We are given a circle and the sequence of segment lengths that are encountered as we traverse a ccw-turning path. Each vertex of the path lies on the circle. What is the smallest Euclidean distance between the endpoints of such a path?

Your method will be given radius and a int[] segLength and should return the minimum distance between the endpoints or -1 in case there is no such ccw-turning path.

Definition

Class:: CCWTurning
Method:: minDistance
Parameters:: int, int[]
Returns:: double
Method signature:: double minDistance(int radius, int[] segLength)
(be sure your method is public)

Constraints

segLength will contain between 1 and 30 elements, inclusive.
Each element of segLength will be between 1 and 1,000, inclusive.
radius will be between 1 and 1,000, inclusive.

Examples

8

{5,20,6}

Returns: -1.0

The segment of length 20 cannot be part of a path inscribed in this circle.
5

{10,8}

Returns: 6.0

A ccw-turning 10,8,6 right triangle can be inscribed in this circle.
5

{1,8}

Returns: 7.35989949685296

There are 2 different ccw-turning closed paths that could be inscribed. There is only one turning point. If we choose the less sharp turn we end up at a distance of 8.55989949685296 from the starting point, but if we take the sharper turn we achieve a distance of 7.35989949685296
100

{ 8,2,9,5,11,1,16,13,20, 8,92,2,9,5,11,1,16,13,20,5, 8,2,9,5,11,1,16,13,20,41}

Returns: 0.24782201095555684

int r=100; int[] q={ 8,2,9,5,11,1,16,13,20, 8,92,2,9,5,11,1,16,13,20,5, 8,2,9,5,11,1,16,13,20,41};
100

{2}

Returns: 2.0
5

{10, 10}

Returns: -1.0
7

{1,13,13}

Returns: 8.900858740315613
937

{238, 457, 69, 400, 387, 8, 86, 56, 343, 131, 73, 382, 142, 194, 100, 106, 395, 203, 936, 291, 173, 825, 353, 242, 438, 118, 190, 135, 1}

Returns: 3.2930647199460132

437185 {238536, 457240, 69892, 400658, 387791, 8366, 86386, 56351, 343258, 131305, 73087, 382059, 142276, 194652, 100118, 106756, 395660, 203269, 315265, 291562, 173813, 8256, 353133, 242692, 438434, 118538, 190028, 135095}
500

{499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,498,499}

Returns: 35.775398182583544
4

{2, 4, 2, 1}

Returns: 0.8550799696706053
500

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}

Returns: 394.0436163457748
4

{3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2,3,2}

Returns: 1.0479990371325716
157

{314}

Returns: 314.0
157

{315}

Returns: -1.0
997

{997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997,997}

Returns: 1.184713947204221E-11
499

{998,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,998}

Returns: 2.1394633773861675E-12
499

{997,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,997}

Returns: 4.034487253662523E-12
499

{498,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,499,498}

Returns: 863.1367261401949
47

{94,47,47,47,94}

Returns: 94.0

Statistics

Problem Statement for "CCWTurning"

Problem Statement

Definition

Constraints

Examples