BuildTheRoads | Topcoder Archive

Problem Statement

There are N villages in the kingdom of Byteotia. Currently the villages are connected by a random tangle of muddy paths. To ease the life of the villagers, the king would like to build a network of paved roads. There should be N-1 paved roads, each connecting two villages in a straight line. It should be possible to travel from each village to each other village using only the paved roads. The spread of a road network is the longest distance one needs to travel between some pair of villages. The king wants you to construct a road network with the smallest possible spread.

The villages are described by two int[]s x and y. For each i, village number i is a point with coordinates (x[i], y[i]). The distance between two villages is the Euclidean distance between the corresponding points. There are no three points that lie on the same straight line.

Return the minimal possible cost for the road network.

Definition

Class:: BuildTheRoads
Method:: minimalCost
Parameters:: int[], int[]
Returns:: double
Method signature:: double minimalCost(int[] x, int[] y)
(be sure your method is public)

Notes

Your return value must have an absolute or relative error less than 1e-9.
Should your road network contain crossings between paved roads, all such crossings will be handled by building bridges. In other words, each paved road can only be used for travel between its two endpoints.

Constraints

N will be between 2 and 200, inclusive.
Each of x, y will contain exactly N elements.
Each element of x will be between -10,000 and 10,000, inclusive.
Each element of y will be between -10,000 and 10,000, inclusive.
No two of the N points described by x and y will be identical.
No three of the N points described by x and y will be collinear.

Examples

```
{1,2,4,3}
```
```
{1,2,3,5}
```
```
Returns: 5.39834563766817
```
There are four villages in points (1,1), (2,2), (4,3), and (3,5). Optimal network consists of roads that connect village 1 to each of the villages 0, 2, and 3. The two villages that are the farthest apart are villages 2 and 3. When travelling from 2 to 3, you need to travel via 1. The length of your route is sqrt(5) + sqrt(10).
```
{1,2,4,3,3}
```
```
{1,2,3,5,4}
```
```
Returns: 5.06449510224598
```
Adding village number 4 at coordinates (3,4) changes the optimal network. The longest path now goes through villages 0, 1, 4, and 2; its length is 2*sqrt(2) + sqrt(5).

{-10000,10000}

{-10000,10000}

Returns: 28284.2712474619

{-1,-2,1,0,-1,0,1}

{2,1,1,0,-2,-1,-1}

Returns: 4.47213595499958

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.