Travel optimization P62842


pdf   zip


Consider a two-dimensional world with no obstacles. You must go from point A to point B, and then return to A. When traveling, you can either walk or take the train. There are only two train stations, C and D, with trains going in both directions. On the outside, stations have a public timer displaying the time until the next train. When looking at the timer, you can decide to either wait for the next train, or to walk to your destination. Assume that the time displayed when arriving at a station follows a uniform distribution from 0 to U, and that there is no correlation between the schedule of the trains in the two directions. Suppose that it takes no time to enter or leave a train.

Given the positions of the four differents points A, B, C and D, the walking speed W, the train speed T, and the constant U, can you compute the minimum expected time to go from A to B, and from B to A, assuming a perfect strategy?


Input consists of several cases with real numbers, each with the coordinates of A, B, C and D, followed by W, T, and U. Assume T > W > 0 and U > 0.


For each case, print the expected time to go from A to B, and to go from B to A, both with four digits after the decimal point. The input cases have no precision issues.

Public test cases
  • Input

    0 0  10 0  0 30  10 30
    1 4 2
    0 0  10 0  0 2  10 2
    1 4 2
    3 3  1 0  0 2  4 1
    1 2 1000
    0.2 -42.23  10.2 -42.23  2.2 -42.23  12.2 -42.23
    2.5 8.9 4.3


    10.0000 10.0000
    7.5000 7.5000
    3.6056 3.6056
    3.8106 4.0000
  • Information
    Ivan Geffner
    Official solutions
    User solutions