Description

Mirko found a wooden board and $n$ nails in the attic. He quickly hammered the nails into the board. We model the board on the coordinate plane, and the nails are points on it. No two nails have the same $x$ coordinate or the same $y$ coordinate.

To have more fun, Mirko stole his sister’s elastic hair tie, put it around all the nails, and then let go. The elastic naturally tightens around the nails.

Then Mirko repeats these steps, making sure that at least three nails remain on the board:

1. Record the area of the shape enclosed by the elastic band.

2. Choose the leftmost, rightmost, topmost, or bottommost nail on the board.

3. Remove the chosen nail from the board. The elastic band again tightens around the outermost nails still left on the board.

Now we are given which nail Mirko chooses each time he performs step $2$. Write a program to compute the area recorded each time step $1$ is performed.

Input Format

The first line contains an integer $n$, the number of nails.

The next $n$ lines each contain two integers $x_i$ and $y_i$, separated by spaces, giving the coordinates of the $i$-th nail.

The following line contains a string of length $n - 2$, consisting of the characters L, R, U, D, representing the nail Mirko removes. These characters mean:

• L: remove the leftmost nail (the nail with the smallest $x$ coordinate).
• R: remove the rightmost nail (the nail with the largest $x$ coordinate).
• U: remove the topmost nail (the nail with the largest $y$ coordinate).
• D: remove the bottommost nail (the nail with the smallest $y$ coordinate).

Output Format

Output $n - 2$ lines. Each line contains a floating-point number: the area computed each time step $1$ is performed, rounded to one digit after the decimal point.

5
1 4
2 2
4 1
3 5
5 3
LUR

9.0
6.5
2.5

8
1 6
2 4
3 1
4 2
5 7
6 5
7 9
8 3
URDLUU

34.0
24.0
16.5
14.0
9.5
5.0

Hint

Sample #2 Explanation.

The above figures correspond to the input of sample #2. The program should simulate the six steps in order.

Constraints

• For $50\%$ of the testdata, $3 \leq n \leq 1000$ is guaranteed.
• For $100\%$ of the testdata, $3 \leq n \leq 3 \times 10^5$ is guaranteed.

Notes

This problem is translated from COCI2008-2009 CONTEST #2 CAVLI. Translator:

https://www.luogu.com.cn/user/115711

Translated by ChatGPT 5