Connection Status:
Competition Arena > WalkingDistance

WalkingDistance

SRM 417 · 2008-09-10 · by ivan_metelsky

SRM 417 · 2008-09-10 · by ivan_metelsky · Geometry, Graph Theory, Math
Class Name: WalkingDistance
Return Type: double
Method Name: getLongestShortest
Arg Types: (vector<int>, vector<int>, vector<string>)
Problem Statement

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.

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)
{0,1}
{0,1}
{"NY","YN"}
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,1,0}
{0,0,1,1}
{"NYNY","YNYN","NYNY","YNYN"}
Returns: 2.0
3)
{-1000,-1000,1000,1000}
{-1000,1000,1000,-1000}
{"NYNY","YNYN","NYNY","YNYN"}
Returns: 4000.0
4)
{0,1,2,2}
{0,0,1,-1}
{"NYNN","YNYY","NYNY","NYYN"}
Returns: 3.414213562373095
5)
{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).

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

Coding Area

Language: C++17 · define a public class WalkingDistance with a public method double getLongestShortest(vector<int> x, vector<int> y, vector<string> streets) · 160 test cases · 2 s / 256 MB per case

Submitting as anonymous