ConnectingAsteroids | Topcoder Archive

Problem Statement

A multinational firm wants to create a communication network between asteroids. To achieve this, they will use brand new equipment where communication is made between pairs of stations in the following manner:
Each station throws a ray pointing directly to the other, and at the point where both rays meet, information is exchanged and brought back to the original stations. It is possible to save power this way because the maximum ranges of the two stations are combined to produce a greater range. For example, if two stations are ten miles apart, it is sufficient for one station to have power for a range of 6 miles and the other to have power for a range of 4 miles.

The firm wants every asteroid to be able to communicate directly with each of the other asteroids. One station will be bought for each asteroid. The cost of this equipment increases rapidly with power, so it is always better to buy stations that are as weak as possible while still providing enough range for the required communication. There are multiple configurations that will satisfy the firm's requirement. Choose the one where the range of the most powerful station is minimized, and if there are still multiple configurations, choose the one among them where the range of the second most powerful station is minimized, and so on.

You will be given the 3-D coordinates of the asteroids in three int[]s x, y and z. The x, y and z coordinates of the ith asteroid will be given by the ith element of x, y and z respectively. Choose the stations' ranges as described above and return the range of the least powerful station.

Definition

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

Notes

The returned value must be accurate to within a relative or absolute value of 1E-9.
The range of a station can be any non-negative real number.

Constraints

x will have between 2 and 50 elements, inclusive.
x, y and z will have the same number of elements.
All elements of x, y and z will be between -10000 and 10000, inclusive.
All asteroids will have different positions.

Examples

```
{0,0,0,0}
```
```
{0,3,0,3}
```
```
{0,0,4,4}
```
```
Returns: 2.5
```
Here we have a rectangle with asteroids at its vertices. Since the furthest asteroid from each vertex is at the opposite corner, we can make the range of each station exactly half of that distance. +----+ |\ | 4 | \ | | 5\ | | \| +----+ 3

{-10000,10000}

{-10000,10000}

{-10000,10000}

Returns: 17320.508075688773

{0,34,65,-33}

{3453,3453,-23,272}

{-3453,-123,-987,-1}

Returns: 1666.6489981745426

{5498,-9425,-2687,7918,-1205,-6704,-420,-2404,-5955,-8176,-3227,-6612,-648,-1860,-7616,-1770,-925}

{-7784,1176,4844,-6817,6763,1826,-9180,-9230,-7492,698,-7718,-3200,-1373,5931,-2410,2078,9913}

{-5289,-8218,-9141,-5999,-8364,-1671,2870,8781,-3659,2053,-3932,-9912,2572,-3995,-6251,6009,-372}

Returns: 5226.572027143964

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.