Connection Status:
Competition Arena > AirlineInternet

AirlineInternet

SRM 393 · 2008-03-11 · by StevieT

SRM 393 · 2008-03-11 · by StevieT · Geometry, Graph Theory, Search
Class Name: AirlineInternet
Return Type: double
Method Name: minimumRange
Arg Types: (vector<string>, vector<string>)
Problem Statement

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.

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)
{"0 0","100 0"}
{"0 1 0 100","0 1 10 110","0 1 20 120","0 1 30 130","0 1 40 140"}
Returns: 30.0

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

Coding Area

Language: C++17 · define a public class AirlineInternet with a public method double minimumRange(vector<string> airportLocations, vector<string> flights) · 54 test cases · 2 s / 256 MB per case

Submitting as anonymous