Minimum Separation Distance of Two Walkers

Two persons start walking on an infinite 2D plane along paths parallel to the coordinate axes. At each second, each person moves exactly 1 unit in one of the four cardinal directions: up, down, left, or right. Given their starting positions and walking directions, compute the minimum Euclidean distance between the two persons observed after their move at each full second (i.e. at t = 1, 2, 3, ...). Note that distances measured at times between the seconds are not considered.

Formally, let the first person start from \( (x_1, y_1) \) and move in the direction \( d_1 \) and the second person start from \( (x_2, y_2) \) and move in the direction \( d_2 \). Their positions at time \( t \) (in seconds) are given by:

[ \begin{aligned} P_1(t) &=\big(x_1 + t \cdot \Delta x(d_1),; y_1 + t \cdot \Delta y(d_1)\big),\ P_2(t) &=\big(x_2 + t \cdot \Delta x(d_2),; y_2 + t \cdot \Delta y(d_2)\big), \end{aligned} ]

where \( \Delta x(d) \) and \( \Delta y(d) \) are defined as follows:

• If \( d = \texttt{R} \) then \( (\Delta x,\Delta y)=(1,0) \).
• If \( d = \texttt{L} \) then \( (\Delta x,\Delta y)=(-1,0) \).
• If \( d = \texttt{U} \) then \( (\Delta x,\Delta y)=(0,1) \).
• If \( d = \texttt{D} \) then \( (\Delta x,\Delta y)=(0,-1) \).

The Euclidean distance at time \( t \) is

[ d(t)=\sqrt{\big((x_1-x_2) + t\cdot(\Delta x(d_1)-\Delta x(d_2))\big)^2+\big((y_1-y_2) + t\cdot(\Delta y(d_1)-\Delta y(d_2))\big)^2}. ]

Your task is to determine the minimum value of \( d(t) \) over all integer seconds \( t \ge 1 \). It is guaranteed that with the input constraints, an answer exists.

inputFormat

The input consists of a single line containing six space-separated items:

• An integer \( x_1 \) and an integer \( y_1 \): the starting coordinates of the first person.
• A character \( d_1 \) (one of R, L, U, D): the direction of the first person.
• An integer \( x_2 \) and an integer \( y_2 \): the starting coordinates of the second person.
• A character \( d_2 \) (one of R, L, U, D): the direction of the second person.

For example: 0 0 R 2 0 L.

outputFormat

Output a single line containing the minimum Euclidean distance observed (after an integer number of seconds), formatted to 6 decimal places.

For instance, for the input above, the output should be 0.000000.

sample

0 0 R 2 0 L

0.000000