Problem Statement |
| | There is a country with N cities. The cities are located on a two-dimensional plane. The coordinates of the i-th city are given in cityX[i] and cityY[i]. The 0-th city is the capital city while the (N-1)-th city is the center of the market (0-based indexing). Each city is assumed to be a point.
The distance that a citizen needs to travel from one city to another is equal to the Euclidian distance between them. A citizen can travel directly from one city to another if the Euclidian distance does not exceed maxDirect (since they can only carry a limited amount of supplies). Hence, if a citizen wants to go from the capital city to the center of the market then he may need to visit some cities in the journey to restock some supplies.
The king wants to reduce the minimum total distance that a citizen needs to travel from the capital city to the center of the market. He wants this minimum distance to not exceed maxTravel. In order to do so he will create some new cities in the country (he can do so at any coordinates not necessarily integer).
Return the minimum number of new cities needed to be built to achieve his target or -1 if it is impossible. |
| |
Definition |
| | | Class: | BuildingCities | | Method: | findMinimumCities | | Parameters: | int, int, int[], int[] | | Returns: | int | | Method signature: | int findMinimumCities(int maxDirect, int maxTravel, int[] cityX, int[] cityY) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The Euclidian distance between two points (X1,Y1) and (X2,Y2) is defined as the square root of ((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)). |
| |
Constraints |
| - | maxDirect and maxTravel will be between 1 and 2000, inclusive. |
| - | cityX and cityY will contain between 2 and 50 elements, inclusive. |
| - | cityX and cityY will contain the same number of elements. |
| - | Each element of cityX and cityY will be between 0 and 2000, inclusive. |
| - | All cities will have distinct locations. |
| - | To avoid precision problems, if the answer for an input is X >= 0, then it will be possible to build X cities in such way that the minimal travel distance between the capital city and the center of the market is at most maxTravel - 1e-5, and any way of building fewer than X cities will result in this minimal distance being at least maxTravel + 1e-5. |
| |
Examples |
| 0) | |
| | 1 | 5 | {0,0,0,1,2,2,3} | {0,1,2,2,2,1,1} |
| Returns: 1 | | Without adding new cities the minimum distance is 6. By building a city at (1,1) the minimum distance can be reduced to 4. |
|
|
| 1) | |
| | |
| 2) | |
| | 2 | 15 | {0,5,2,3,1,8,6,4,7,9,10} | {0,5,2,3,1,8,6,4,7,9,10} |
| Returns: 0 | | Sometimes no new cities need to be built. |
|
|
| 3) | |
| | | Returns: -1 | | The minimum distance between the two cities will always exceed 5. |
|
|
| 4) | |
| | |