UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1837. [CROATIAN2009]cavli 凸包1

统计 下载数据

Description

给你N个点,请循环完成下列任务 1:求出这N个点的凸包的面积 2:拿掉最左或最右或最上或最下的一个点,当点的个数不足三个时停止

Input

第一行,一个数字N 接下来N行,每行两个数Xi,Yi 接下来,一个字符串,表示每次拿走的点(仅为UDLR代表上下左右)

Output

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

Sample Input

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

Sample Output

4399.0
3795.0
3373.0
2227.0
1935.5
1243.0
775.0
675.0

Hint

3<=N<=300000
1<=Xi,Yi<=1000000000
不存在两个点 X坐标或 Y坐标相同

Source

COCI 2008/2009 Contest #2.