Under construction

Still being built. Things may change

Area between a lattice path and its chord

Time limit8sMemory limit512 MB

Summary
Given a monotone path of up and right steps, compute the total area between the path and the straight chord from start to end.
Level

Medium6 of 10

Topics
Geometry, Prefix sum, Math, Implementation
Solved
No attempts yet

Problem

Consider a path on the plane that starts at the origin and can move only up or right. The path is written as a string of 'U' and 'R' characters. 'U' moves one unit up and 'R' moves one unit to the right. In the figure below, the path given by the string RRRURRUUURRRRRUUR is drawn as a thick line.


Figure 1: a sample 2D path

Now draw the straight line that joins the origin to the last point of the path. It is the dotted line in the figure. Compute the total area that lies between this line and the path, shown in gray in the figure.

When the path crosses the line several times, add up the areas of all the separate regions. If the path consists only of 'R' or only of 'U', the line lies on top of the path and the area is 00.

Input

The input consists of one or more test cases, one per line. Each line holds a path string of one or more 'U' and 'R' characters, followed by the letter 'S'.

Every path in the input can be drawn on a grid of size 1000×10001000 \times 1000. That is, one path contains at most 10001000 letters 'R' and at most 10001000 letters 'U'.

The last line of the input is a single 'S' and is not a test case.

Output

For each test case, print the area on its own line. Round to three digits after the decimal point and always print all three digits.

Examples3

  1. Example 1

    Input
    RRRURRUUURRRRRUURS
    RUURS
    S
    
    Expected output
    8.515
    1.000
    
  2. Example 2

    Input
    RS
    US
    RUS
    URS
    RRUUS
    UURRS
    S
    
    Expected output
    0.000
    0.000
    0.500
    0.500
    2.000
    2.000
    
  3. Example 3

    Input
    RRRRRUUUUUS
    RUUUUURRRRS
    RRRRUUUUURS
    URURURURURS
    RRUURRUURRS
    S
    
    Expected output
    12.500
    8.500
    8.500
    2.500
    3.333