Connection Status:
Competition Arena > BuildTheRoads

BuildTheRoads

2018 TCO Semi 2 · 2018-11-14 · by monsoon

2018 TCO Semi 2 · 2018-11-14 · by monsoon · Geometry, Graph Theory
Class Name: BuildTheRoads
Return Type: double
Method Name: minimalCost
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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
0)
{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)
{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).

2)
{-10000,10000}
{-10000,10000}
Returns: 28284.2712474619
3)
{-1,-2,1,0,-1,0,1}
{2,1,1,0,-2,-1,-1}
Returns: 4.47213595499958
4)
{6,5,3,2,6}
{7,7,2,6,1}
Returns: 10.508270432752164

Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BuildTheRoads with a public method double minimalCost(vector<int> x, vector<int> y) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous