Minimum Bounding Box

题目描述

平面上有 $N$ 个点。第 $i$ 个点的初始坐标为 $(x_i, y_i)$。现在，每个点以速度为每秒 1 的速度开始运动，运动方向与 $x$ 轴或 $y$ 轴平行。给出字符 $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$ . . . $x_N$ $y_N$ $d_N$

输出格式

输出 $(x_{max} - x_{min}) \times (y_{max} - y_{min})$ 的最小可能值。 当你的输出与裁判的输出的绝对或相对误差不超过 $10^{-9}$ 时，将被视为正确。

2
0 3 D
3 0 L

0

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

97.5

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

273

提示

$1 \leq N \leq 10^5$ $-10^8 \leq x_i,\ y_i \leq 10^8$ $x_i$ 和 $y_i$ 是整数。 $d_i$ 是 $R$、$L$、$U$ 或 $D$。三秒后，两个点会在原点相遇。此时所求的值为 $0$。
答案可能不是整数。

标签: AtCoder|abc130F

来源

AtCoder|abc130F