Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P134SUMI - SUM4 I - Bàn cờ

Tí vào nhà kho phát hiện ra chiếc bàn cờ cũ của mình, nhưng không hiểu sao đã bị ai phá hỏng, N chiếc đinh đã bị đóng lên trên bàn cờ. Bàn cờ được đánh dấu theo hệ tọa độ Oxy. Tí nghĩ ra một trò khá thú vị.

Tí đã lấy trộm dây buộc tóc của em gái, rồi để chiếc dây chun bọc kín tất cả các chiếc đinh. Theo bản chất đàn hồi tự nhiên, chiếc dây sẽ tự co lại, và nó chiếm giữ đa giác lồi lớn nhất tạo bởi các chiếc đinh.

Tí thực hiện lần lượt các thao tác sau, cho đến khi còn lại 3 chiếc đinh trên bàn cờ.

1. Viết ra diện tích mà chiếc dây chiếm giữ.

2. Chọn ra 1 chiếc đinh ở ngoài cùng bên trái, bên phải, bên trên hoặc bên dưới.

3. Nhổ đi chiếc đinh đã lựa chọn. Do đó, chiếc dây sẽ tự đàn hồi và co lại về vị trí mới.

Cho biết trước chuỗi sự lựa chọn các chiếc đinh của Tí, nhiệm vụ của bạn là tính toán diện tích mà chiếc dây buộc tóc chiếm giữ tại mỗi bước.

Input

Dòng đầu tiên là số nguyên N (3 ≤ N ≤ 300 000), là số chiếc đinh trên bàn cờ.

N dòng tiếp theo, mỗi dòng gồm 2 số nguyên x_i, y_i (1 <= x_i, y_i <= 1 000 000 000) là tọa độ của chiếc đinh thứ i. Không có 2 chiếc đinh nào có cùng hoành độ hoặc tung độ.

Dòng tiếp theo là mỗi chuỗi các kí tự 'L', 'R', 'U' và 'D' có độ dài N – 2. Các chữ cái đại diện cho:

· 'L' cho chiếc đinh ở ngoài cùng bên trái (hoành độ x nhỏ nhất),

· 'R' cho chiếc đinh ở ngoài cùng bên phải (hoành độ x lớn nhất),

· 'U' cho chiếc đinh ở trên cùng (tung độ y lớn nhất),

· 'D' cho chiếc đinh ở dưới cùng (tung độ y nhỏ nhất).

Output

In ra N-2 số, mỗi số trên một dòng. Mỗi số lần lượt là diện tích mà Tí đã ghi chép lại, độ chính xác là 1 chữ số sau dấu thập phân.

Example

Test 1:

Input:

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

Output:

9.0
6.5
2.5

 

Test 2:

Input:

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

Output:

34.0
24.0
16.5
14.0
9.5
5.0

Giải thích test 2:

 


Được gửi lên bởi:adm
Ngày:2013-07-31
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.