Problem Statement |
| | An airline wishes to supply passengers with Internet access on its flights. To do so, it is going to to install powerful radio transceivers on all of its aircraft and at the airports it operates from. The airports will be connected to the Internet and the aircraft will be able to access the connection via a radio link to any airport that is within the range of its tranceiver. Aircraft will also be able to relay the Internet connection on to other aircraft that are within range, so even if an aircraft cannot communicate directly with an airport, it may be able to access the Internet via another aircraft. The cost of the radio equipment is proportional to its range and the airline wishes to supply the Internet connection at minimal cost. It therefore wants your help in determining the minimum transceiver range required such that all of the aircraft can access the Internet all of the time.
The area that the airline operates in is represented as a 2-D cartesian plane. You are given a String[] airports containing the locations of the airports that the airline operates from. Each element will contain two space-separated integers, formatted without leading zeros, giving the x- and y-coordinates of an airport. You are also given the flight-schedule in a String[] flights. Each element of flights describes a single flight and will be formatted "<start> <destination> <take-off time> <landing time>" (quotes for clarity). All elements are integers formatted without leading zeros. <start> and <destination> reference zero-based indexes of airports in airports. The aircraft starts out at the airport referenced by <start> at time <take-off time>, and flies in a straight line at constant speed to the airport referenced in <destination>, arriving at <landing time>. All radio tranceivers have the same range R and an aircraft can communicate with an airport or another aircraft if the in-plane distance between the two is no greater than R. An aircraft can access the Internet if it can either communicate with an airport, or it can communicate with another aircraft that can access the Internet (directly or indirectly). Return a double containing the minimum value of R which ensures that all aircraft can access the Internet at all times. |
| |
Definition |
| | | Class: | AirlineInternet | | Method: | minimumRange | | Parameters: | String[], String[] | | Returns: | double | | Method signature: | double minimumRange(String[] airportLocations, String[] flights) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Your return value must be accurate to within an absolute or relative tolerance of 1E-9. |
| |
Constraints |
| - | airportLocations will contain between 2 and 10 elements, inclusive. |
| - | Each element of airportLocations will contain 2 space-separated integers, formatted without leading zeros, between 0 and 1000, inclusive. |
| - | The elements of airportLocations will be distinct. |
| - | flights will contain between 1 and 20 elements, inclusive. |
| - | Each element of flights will be formatted "<start> <destination> <take-off time> <landing time>" (quotes for clarity). |
| - | <start> and <destination> will be integers, formatted without leading zeros, between 0 and N-1, inclusive, where N is the number of elements in airportLocations. |
| - | <take-off time> and <landing time> will be integers, formatted without leading zeros, between 0 and 1000, inclusive. |
| - | In each element of flights, <start> and <destination> will be distinct and <take-off time> will be strictly less than <landing time>. |
| |
Examples |
| 0) | |
| | {"0 0","100 0"} | {"0 1 0 100"} |
| Returns: 50.0 | | A single aircraft flies between two airports. It is farthest from an airport when it is exactly halfway between them, so the minimum required range is half the distance between the two airports. |
|
|
| 1) | |
| | {"0 0","100 0"} | {"0 1 0 100","0 1 25 125","0 1 50 150","0 1 75 175"} |
| Returns: 25.0 | | This time, four aircraft fly between the same two airports, setting off at intervals of 25 time units. The aircraft closer to the airports can relay the connection to those farther away, so the minimum required range is shorter. |
|
|
| 2) | |
| | {"25 100","0 50","90 150","22 22","60 1","95 8","12 40"} | {"0 1 0 500","2 5 10 300","2 0 100 200"
,"3 6 150 400","4 5 50 450","5 1 0 300"
,"2 6 10 100"} |
| Returns: 64.28201130009927 | |
|
| 3) | |
| | {"0 0","50 0","100 0"} | {"0 1 0 100"} |
| Returns: 25.0 | | All airports have radio transceivers, even if no aircraft fly to or from them. |
|
|
| 4) | |
| | {"417 262","519 592","941 778"} | {"0 1 376 534","0 2 603 763","1 0 137 431"
,"0 1 525 583","2 1 367 551","0 1 953 996"
,"0 1 668 886"} |
| Returns: 246.618769031594 | |
|
| 5) | |
| | {"101 591","283 183","346 696","436 638","738 46"} | {"3 0 855 890","2 0 260 698","3 4 229 743"
,"1 2 519 898","3 1 863 955","4 0 407 993"
,"2 4 872 969","0 3 320 663"} |
| Returns: 298.18759041416865 | |
|
| 6) | |
| | {"152 998","656 487","75 999","913 535"} | {"1 0 347 530","0 3 75 819","3 1 893 935"
,"1 0 971 992","2 0 471 887","2 0 924 955"} |
| Returns: 358.8652253980556 | |
|