PROBLEM STATEMENT
There are N cities in the plane.
For convenience, the cities are numbered 0 through N-1.
For each i, the city number i is represented by the point at coordinates (x[i], y[i]).
The king wants to connect all cities by building exactly N-1 roads.
Each road must connect two cities.
All roads must be straight.
Hence, the length of a road is equal to the Euclidean distance between the two points it connects.
The roads are allowed to cross and even overlap arbitrarily.
(You cannot change roads at a crossing.
Hence, the N-1 roads connect all cities if and only if their topology is a tree.)
The king does not care about roads being short.
However, people often complain if some roads are short and others are long.
Therefore, the king would like to select a set of N-1 roads such that they connect all cities, and
the standard deviation of the sequence of their lengths is as small as possible.
Formally, given a sequence of real numbers (a1,...,aS) we can compute their standard deviation as
follows.
First, let b = ((a1+...+aS) / S) be their mean - i.e., the average of our numbers.
Next, let c = (sum_i (b-ai)^2) be the sum of squared distances of all values from the mean.
Finally, the standard deviation of our sequence is computed as sqrt(c/S).
Note that our sequence will contain exactly N-1 road lengths, hence in the above formulas S will
be equal to N-1.
You are given the vector s x and y with N elements each: the coordinates of the N points.
Compute and return the smallest possible value of the standard deviation of lengths of selected
roads.
DEFINITION
Class:Egalitarianism2
Method:minStdev
Parameters:vector , vector
Returns:double
Method signature:double minStdev(vector x, vector y)
NOTES
-The Euclidean distance between points (a,b) and (c,d) equals sqrt( (a-c)^2 + (b-d)^2 ).
-Your return value must have an absolute or a relative error of less than 1e-9.
CONSTRAINTS
-x will contain between 3 and 20 elements, inclusive.
-x and y will contain same number of elements.
-Each element in x will be between -1,000,000 and 1,000,000, inclusive.
-Each element in y will be between -1,000,000 and 1,000,000, inclusive.
-No two cities will be located in the same place.
EXAMPLES
0)
{0,0,1,1}
{0,1,0,1}
Returns: 0.0
We can build these roads: 0-1, 1-3, 3-2.
1)
{0,0,0}
{0,9,10}
Returns: 0.5
The optimal solution is to build the roads with lengths 9 and 10. (Note that these two roads
overlap, but that is allowed.)
2)
{12,46,81,56}
{0,45,2,67}
Returns: 6.102799971320928
3)
{0,0,0,0,0,0,0}
{0,2,3,9,10,15,16}
Returns: 0.9428090415820632
4)
{167053, 536770, -590401, 507047, 350178, -274523, -584679, -766795, -664177, 267757, -291856,
-765547, 604801, -682922, -404590, 468001, 607925, 503849, -499699, -798637}
{-12396, -66098, -56843, 20270, 81510, -23294, 10423, 24007, -24343, -21587, -6318, -7396, -68622,
56304, -85680, -14890, -38373, -25477, -38240, 11736}
Returns: 40056.95946451828
5)
{-306880, 169480, -558404, -193925, 654444, -300247, -456420, -119436, -620920, -470018, -914272,
-691256, -49418, -21054, 603373, -23656, 891691, 258986, -453793, -782940}
{-77318, -632629, -344942, -361706, 191982, 349424, 676536, 166124, 291342, -268968, 188262,
-537953, -70432, 156803, 166174, 345128, 58614, -671747, 508265, 92324}
Returns: 36879.15127634308
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)2010, TopCoder, Inc. All rights reserved.