TheNewHouseDivOne
SRM 445 · 2009-07-23 · by Vasyl[alphacom]
Problem Statement
John is obsessed with security. He has several old houses and he wants to build one new. John is very afraid of thieves, so he will choose the location of the new house using the following method. From each of his old houses, he will measure the Manhattan distance to the new house. He will then take the k-th (1 based) shortest distance. The location that minimizes this distance will be the location of his new house.
You are given the locations of his old houses in
Notes
- The returned value must be accurate to within a relative or absolute value of 1E-9.
- The Manhattan distance between two points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.
- Several houses can be located at the same point.
Constraints
- x will contain between 1 and 50 elements, inclusive.
- x and y will contain the same number of elements.
- Each element of x will be between -50 and 50, inclusive.
- Each element of y will be between -50 and 50, inclusive.
- k will be between 1 and the number of elements in x, inclusive.
{-1, -1, 1, 1}
{-1, 1, -1, 1}
3
Returns: 2.0
One of the optimal ways is to build a new house at (0, 0).
{-1, -1, 1, 1}
{-1, 1, -1, 1}
2
Returns: 1.0
And here we have four possible locations for the new house - (-1, 0), (1, 0), (0, -1) and (0, 1).
{4, 4, 4, 4, 4, 3, 3, 5, 5}
{7, 7, 7, 4, 4, 5, 6, 5, 6}
9
Returns: 1.5
Some houses are located at the same point.
{30, -15, 24, -23, 43, -8, -6, -47, 23, -11, 43, 6, -18, 44, -46, 16, 32, 31, 13, 9, 22, 25, 4, -44, 38, -41, -20, 41, -35, 7, 25, 39, -36, -20, -5, -38, -15, -22, 0}
{-45, -7, -33, 31, -8, -33, -20, -14, -50, -48, -31, 35, -24, -31, -11, 41, -41, -11, 46, -1, -5, 5, -39, -26, -40, -9, 16, 38, -30, 34, 46, -17, -27, 33, -38, 28, 46, -16, -46}
13
Returns: 32.0
{22, -37, -39, 29, -28, 17, -13, 27, -40, -31, 15, 23, -47, 28, -7, 46, -36, -15, 8, 11, 49, -41, -24, -3, -46, -22, 49, -44, 10, -12, 26, -7, -28, 2, -44, -8, -14}
{32, 8, -38, 47, 26, 31, 3, 21, 49, 26, -7, 45, 22, 40, 11, -21, -21, 1, 40, -46, 14, -7, -8, 46, -33, 39, -1, -18, 3, -38, -27, 37, 26, -31, 26, 11, -49}
34
Returns: 69.5
Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheNewHouseDivOne with a public method double distance(vector<int> x, vector<int> y, int k) · 106 test cases · 2 s / 256 MB per case