A7649. [ABC130F] Minimum Bounding Box
编程题
普及+/提高
知识点
题目描述
平面上有 $N$ 个点，第 $i$ 个点的坐标是 $(x_i, y_i)$。现在，每个点开始沿着 $x$ 轴或 $y$ 轴方向以 $1$ 格每秒的速度移动。字符 $d_i$ 表示第 $i$ 个点的方向：
* 如果 $d_i=$
* 如果 $d_i=$
* 如果 $d_i=$
* 如果 $d_i=$
点开始移动后，你可以选择任意一个时刻（包括刚刚开始的那个时刻）停止所有点。停止后，分别记 $x_{max},x_{min}$ 为 $N$ 个点中 $x$ 坐标的最大值、最小值；同样，记 $y_{max},y_{min}$ 为 $N$ 个点中 $y$ 坐标的最大值、最小值。
你需要找出 $(x_{max}-x_{min})\times(y_{max}-y_{min})$ 的最小值并输出这个值。
* 如果 $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$
> $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}$ 以内时，你的输出会被认为是正确的。
当与答案的相对误差在 $10^{-9}$ 以内时，你的输出会被认为是正确的。
输入输出样例
输入 #1
2 0 3 D 3 0 L
输出 #1
0
输入 #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
273
说明/提示
* $1 \le N \le 10^5$。
* $-10^8 \le x_i, y_i \le 10^8$。
* $x_i,y_i$ 都是整数。
* $d_i$ 是
#### 样例 1/样例 4
第 $3$ 秒，两点在原点相遇，此时的答案是 $0$。
#### 样例 2/样例 5
答案也许不是整数。
* $-10^8 \le x_i, y_i \le 10^8$。
* $x_i,y_i$ 都是整数。
* $d_i$ 是
R、L、U、D 的其中之一。#### 样例 1/样例 4
第 $3$ 秒，两点在原点相遇，此时的答案是 $0$。
#### 样例 2/样例 5
答案也许不是整数。