Problem Statement |
| | A map of the city consists of a number of streets connecting several junctions. All the streets are straight line segments connecting two junctions, organized in such a way that starting at any junction and walking along the streets one can reach any other junction. The walking distance between two points (each either a junction or some intermediate point of a street) in the city is the shortest path from the first point to the second, if you are allowed to walk only along the streets. The length of the street is the Cartesian distance between its ends. Streets never intersect outside the junctions. Tunnels and overpasses are used whenever necessary to achieve this (see example 1 for further clarification).
Given a map of the city, your goal is to find the maximal walking distance among any two points in the city. The map of the city is provided as follows. You are given two int[]s x and y, each of the same length N. These two int[]s represent N junctions with Cartesian coordinates (x[i], y[i]) for i = 0..N-1. You are also given a String[] streets, where the j-th element of streets[i] is 'Y' if the junctions i and j are connected by a street, and 'N' otherwise. |
| |
Definition |
| | | Class: | WalkingDistance | | Method: | getLongestShortest | | Parameters: | int[], int[], String[] | | Returns: | double | | Method signature: | double getLongestShortest(int[] x, int[] y, String[] streets) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Your return value must have an absolute or relative error less than 1e-9. |
| |
Constraints |
| - | x and y and streets will each contain between 2 and 50 elements, inclusive. |
| - | x, y and streets will have the same number of elements. |
| - | Each element of x and y will be between -1000 and 1000, inclusive. |
| - | Each element of streets will contain exactly n characters, where n is the number of elements in streets. |
| - | Each element of streets will contain only 'N' and 'Y' characters. |
| - | The i-th character of the i-th element of streets will always be 'N'. |
| - | The i-th character of the j-th element of streets will always be equal to the j-th character of the i-th element of streets. |
| - | All junctions represented by x and y will be distinct. |
| - | There will be a path between every pair of junctions. |
| |
Examples |
| 0) | |
| | | Returns: 1.4142135623730951 | | There are just two junctions conntected by a road. So the answer is the length of the street, which is the square root of 2. |
|
|
| 1) | |
| | {0,2,2,0} | {0,0,2,2} | {"NNYY","NNYY","YYNN","YYNN"} |
| Returns: 4.82842712474619 | | Both points on which this maximal shortest distance is achieved have coordinates (1, 1), but they are located on different streets.
|
|
|
| 2) | |
| | {0,1,0} | {0,0,1} | {"NYY","YNY", "YYN"} |
| Returns: 1.7071067811865475 | | The three junctions form a right isosceles triangle. Two points for which the maximal walking distance is achieved are (0,0) and (1/2, 1/2). |
|
|
| 3) | |
| | {0, 1, 2} | {0, 1, 2} | {"NYY", "YNN", "YNN"} |
| Returns: 4.242640687119286 | |
|