RobotConstruction | Topcoder Archive

Problem Statement

Your mother asked you to water all her flowers. You are lazy, so you want to construct a railrobot which will be able to water the flowers for you. You have several rail segments, with the i-th segment being of length segment[i], and you want you robot to be able to water all your flowers. The construction process goes as following: you select some of the segments, join them in some order and fix the start of the first segment to point (0, 0), where the robot's base is located.

Once you've constructe the railway, your robot starts its job. Robot changes the angles between rail segments and rotates the first segment around the base in such way that the end of the last segment will coincide with the first flower (so the robot can reach it). Once the robot reached the first flower, it sets up all angles and rotates the first segment once more to reach the second flower, and so on. Robot can not change neither the selection of the rails, nor their order.

You don't want to distress your mother, so the robot must be able to reach and water each flower. All roborails are of zero thickness, so they are very fragile and the robot can not rotate them in such way that any rail will intersect or touch any other rails. Of course, two consecutive rails may touch in the point where they ar joined (but one rail can not go along another rail, see example 3 for clarification). More exactly, any two robot's segments can have common points only if they are consecutive, and in that case there can be just one common point - their common end.

The locations of your flowers are given in a String[] flowers. Element i of flowers will be formatted "x y" (quotes for clarity), where (x, y) will represent the coordinates of the i-th flower. Return the minimum total length of segments you should select to construct the robot, or return -1 if it is impossible.

Definition

Class:: RobotConstruction
Method:: minimumLength
Parameters:: int[], String[]
Returns:: int
Method signature:: int minimumLength(int[] segments, String[] points)
(be sure your method is public)

Constraints

segments will contain between 1 and 50 elements, inclusive.
Each element of segments will be between 1 and 100, inclusive.
points will contain between 1 and 50 elements, inclusive.
Each element of points will be formatted "x y" (quotes for clarity), where both x and y are integers between -100 and 100, inclusive, with no extra leading zeros.
All elements of points will be distinct.
No element of points will be equal to "0 0".

Examples

```
{1, 3, 5}
```
```
{"3 4"}
```
```
Returns: 5
```
You need to reach a point which has distance 5 from (0, 0). To do this, you can just take one segment of length 5.
```
{2, 2, 2, 2, 2}
```
```
{"-4 -3"}
```
```
Returns: 6
```
Take 3 segments of length 2.
```
{1, 1}
```
```
{"0 3"}
```
```
Returns: -1
```
With only two segments of length 1 you can't reach the point which is on distance 3 from origin.
```
{2, 5}
```
```
{"3 0"}
```
```
Returns: -1
```
A single segment of length 2 is not enough. A single segment of length 5 is too much. As the angle between segments can't be exactly 180 degrees, both segments also don't help.
```
{98, 100, 98}
```
```
{"1 0"}
```
```
Returns: 196
```
Take two segments of length 98.

{8, 1, 9, 1, 6}

{"-1 -5", "-4 -8", "6 -3", "-3 9", "-7 1"}

Returns: 14

Take segments with length 6 and 8.

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.