题目描述

给你 $N$ 个点,请循环完成下列任务：

1. 求出这 $N$ 个点的凸包的面积。

2. 拿掉最左或最右或最上或最下的一个点，当点的个数不足三个时停止。

输入格式

第一行，一个数字 $N$。

接下来 $N$ 行,每行两个数 $X_i,Y_i$。

接下来，一个字符串，表示每次拿走的点（UDLR 分别代表上下左右）。

输出格式

输出有 $N-2$ 行，每行一个实数，保留一位小数。

10
68 94
96 75
14 65
72 71
18 44
56 13
98 57
30 25
55 82
22 21
LRDUUUDL

4399.0
3795.0
3373.0
2227.0
1935.5
1243.0
775.0
675.0

提示

$3\le N\le 3\times 10^5$，$1\le X_i,Y_i\le 10^9$。

保证不存在两个点 $X$ 坐标或 $Y$ 坐标相同。

题目来源

COCI 2008/2009 Contest #2.