A7649 | $[ABC130F] Minimum Bounding Box$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

平面上有 $N$ 个点，第 $i$ 个点的坐标是 $(x_i, y_i)$。现在，每个点开始沿着 $x$ 轴或 $y$ 轴方向以 $1$ 格每秒的速度移动。字符 $d_i$ 表示第 $i$ 个点的方向： * 如果 $d_i=$R，第 $i$ 个点沿 $x$ 轴正方向移动； * 如果 $d_i=$L，第 $i$ 个点沿 $x$ 轴负方向移动； * 如果 $d_i=$U，第 $i$ 个点沿 $y$ 轴正方向移动； * 如果 $d_i=$D，第 $i$ 个点沿 $y$ 轴负方向移动； 点开始移动后，你可以选择任意一个时刻（包括刚刚开始的那个时刻）停止所有点。停止后，分别记 $x_{max},x_{min}$ 为 $N$ 个点中 $x$ 坐标的最大值、最小值；同样，记 $y_{max},y_{min}$ 为 $N$ 个点中 $y$ 坐标的最大值、最小值。 你需要找出 $(x_{max}-x_{min})\times(y_{max}-y_{min})$ 的最小值并输出这个值。

输入来自以下格式的标准输入： > $N$ $x_1$ $y_1$ $d_1$ $x_2$ $y_2$ $d_2$ $\vdots$ $x_N$ $y_N$ $d_N$

输出 $(x_{max}-x_{min})\times(y_{max}-y_{min})$ 可能的最小值。 当与答案的相对误差在 $10^{-9}$ 以内时，你的输出会被认为是正确的。

输入 #1

2
0 3 D
3 0 L

输出 #1

输入 #2

5
-7 -10 U
7 -6 U
-8 7 D
-3 3 D
0 -6 R

输出 #2

97.5

输入 #3

20
6 -10 R
-4 -9 U
9 6 D
-3 -2 R
0 7 D
4 5 D
10 -10 U
-1 -8 U
10 -6 D
8 -5 U
6 4 D
0 3 D
7 9 R
9 -4 R
3 10 D
1 9 U
1 -6 U
9 -8 R
6 7 D
7 -3 D

输出 #3

C++ 编辑器

输入

输出