CCWTurning | Topcoder Archive

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

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.