Area between a lattice path and its chord
Time limit8sMemory limit512 MB
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 .
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 . That is, one path contains at most letters 'R' and at most 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.