Taxi
SRM 300 · 2006-04-27 · by dgoodman
Problem Statement
We know the taxicab distance between two points. We want to know the maximum straight-line distance between them if they lie in the rectangular region { (x,y) | 0<=x<=maxX, 0<=y<=maxY }. Create a class Taxi that contains a method maxDis that is given maxX, maxY, and taxiDis and that returns the largest possible straight-line distance between the two points. If no two points within the given region have the given taxicab distance, return -1.0.
Notes
- A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
Constraints
- maxX and maxY are both between 1 and 1,000,000, inclusive.
- taxiDis is between 0 and 1,000,000, inclusive.
10 3 3 Returns: 3.0
The two points could lie in a straight line parallel to one of the axes. Then the straight-line distance would be the same as the taxicab distance.
10 3 24 Returns: -1.0
No two points with 0<=x<=10, 0<=y<=3, have a taxicab distance between them that is as big as 24.
7 10 13 Returns: 10.44030650891055
(5,0) and (2,10) are two points in this region whose taxicab distance is |2-5| + |10-0| = 13 and whose straight-line distance is sqrt(3*3 + 10*10) = sqrt(109).
5 5 5 Returns: 5.0
4 4 7 Returns: 5.0
Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Taxi with a public method double maxDis(int maxX, int maxY, int taxiDis) · 61 test cases · 2 s / 256 MB per case