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 int[]s x and y.
The i-th old house is located at (x[i], y[i]).
Return the smallest possible k-th distance.
|
| |
Definition |
| | | Class: | TheNewHouseDivOne | | Method: | distance | | Parameters: | int[], int[], int | | Returns: | double | | Method signature: | double distance(int[] x, int[] y, int k) | | (be sure your method is public) |
|
| |
|
| |
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. |
| |
Examples |
| 0) | |
| | {-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, 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). |
|
|
| 2) | |
| | {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. |
|
|
| 3) | |
| | {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 | |
|