This page is still under construction.

Parts of this page are still being built. What you see may change.

Banjo and the lava pit

Time limit3sMemory limit256 MB

Summary
Walk from the start to the destination in the shortest time without staying strictly inside a circular pit for more than t seconds in a row.
Level

Medium7 of 10

Topics
Geometry, Math
Solved
No attempts yet

Problem

Bob is playing a game in which he controls a bear named Banjo. The stage is a two-dimensional coordinate plane, and the goal is to walk Banjo from a start point to a destination. Banjo walks 1 unit per second.

A perfectly circular lava pit lies in the way. Banjo walks across the surface of the pit at the same speed, but if he stays inside the pit for more than tt consecutive seconds, he loses all of his health points. If he steps out of the pit for even a moment his health points reset, and he can step back into the pit if he wants to. The edge of the pit is not inside the pit, so his health points also reset the moment he touches the edge.

Find the minimum time Banjo needs to get from the start point to the destination without ever staying inside the lava pit for more than tt consecutive seconds.

Input

The input has several test cases. Each test case is a single line with eight integers separated by spaces.

x1 y1 x2 y2 xc yc r t

(x1,y1)(x_1, y_1) is where Banjo starts, (x2,y2)(x_2, y_2) is where he must go, and (xc,yc)(x_c, y_c) is the center of the lava pit. rr (1≤r≤100001 \le r \le 10000) is the radius of the pit, and tt (0≤t≤100000 \le t \le 10000) is how long Banjo can stay inside the pit without losing his health points.

All coordinates are integers with −10000≤x,y≤10000-10000 \le x, y \le 10000, and the three points in a test case are distinct. The start point and the destination are not in the lava and not on the edge of the lava.

The last line of the input holds eight 0s. Do not process that line.

Output

For each test case, print the minimum time for Banjo to go from the start to the destination, rounded to exactly two decimal places. Print one number per line, with no spaces inside a line and no blank lines between outputs.

Examples2

  1. Example 1

    Input
    0 0 10 0 5 0 3 5
    0 0 0 0 0 0 0 0
    
    Expected output
    11.00
    
  2. Example 2

    Input
    -5 0 5 0 0 0 3 0
    0 0 0 0 0 0 0 0
    
    Expected output
    11.86