Connection Status:
Competition Arena > KingdomXCitiesandVillagesAnother

KingdomXCitiesandVillagesAnother

Member SRM 503 · 2010-11-01 · by dolphinigle

Member SRM 503 · 2010-11-01 · by dolphinigle · Graph Theory, Greedy
Class Name: KingdomXCitiesandVillagesAnother
Return Type: double
Method Name: determineLength
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

The Grid Kingdom lies on a plane. There are N cities and M villages in the Grid Kingdom, each is a point on the plane. The i-th city is located at coordinates (cityX[i], cityY[i]) and the i-th village is located at coordinates (villageX[i], villageY[i]). Initially, there are no roads in the kingdom, so no village is initially connected to any city.

To improve this, the king has ordered that each village shall be connected to a city by a system of roads. The scheme for building the roads is as follows:

While there exists a village that is not connected to any city:
  1. Pick one unconnected village, call it V.
  2. Select a point, X, which is either a city or a village-that-is-already-connected-to-a-city.
  3. Construct a road from V to X. The length of this road is equal to the Euclidean Distance between points V and X. V is now connected to a city.
You are the king's advisor (for the day) and are in charge of applying the scheme above such that the total length of the constructed roads is minimum. Return this total length.

Notes

  • The Euclidean distance between two points (X1, Y1) and (X2, Y2) is defined as the square root of ((X1-X2)^2 + (Y1-Y2)^2).
  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • cityX will contain between 1 and 50 elements, inclusive.
  • cityY will contain the same number of elements as cityX.
  • Each element in cityX and cityY will be between 0 and 1,000,000, inclusive.
  • villageX will contain between 1 and 50 elements, inclusive.
  • villageY will contain the same number of elements as villageX.
  • Each element in villageX and villageY will be between 0 and 1,000,000, inclusive.
  • The location of all cities will be distinct.
  • The location of all villages will be distinct.
  • There will be no pair of city and village that is located at the same location.
Examples
0)
{1}
{1}
{2,3}
{1,1}
Returns: 2.0

If you pick village 0 first, the total length is 2.0. Otherwise, it's 3.0. So, the minimum possible total length is 2.0

1)
{1,2}
{1,1}
{1,2}
{2,2}
Returns: 2.0
2)
{2}
{2}
{1, 3}
{2, 2}
Returns: 2.0
3)
{5}
{5}
{6}
{6}
Returns: 1.4142135623730951
4)
{0}
{0}
{2}
{2}
Returns: 2.8284271247461903

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

Coding Area

Language: C++17 · define a public class KingdomXCitiesandVillagesAnother with a public method double determineLength(vector<int> cityX, vector<int> cityY, vector<int> villageX, vector<int> villageY) · 167 test cases · 2 s / 256 MB per case

Submitting as anonymous