分数: 600 点
问题陈述
有 N 点位于二维平面中。的初始坐标为 i第一点是 (x_i, y_i)。现在,每个点开始以每秒 1 的速度移动,方向与 x- 或 y- 轴。你被赋予了一个角色 d_i 代表具体方向 i第点移动,如下:
- If d_i =
R, i第一点向正方向移动 x 方向; - If d_i =
L, i第一点向负方向移动 x 方向; - If d_i =
U, i第一点向正方向移动 y 方向; - If d_i =
D, i第一点向负方向移动 y 方向。
您可以在所有点开始移动后(包括它们开始移动的那一刻)在您选择的某个时刻停止它们。 然后,让 x_{max} 和 x_{min} 是其中的最大值和最小值 x- 坐标 分别为 N 点。同样,让 分别为 y_{max} 和 y_{min} 是其中的最大值和最小值 y- 坐标 分别为 N 点。
找到以下的最小可能值 (x_{max} - x_{min}) \times (y_{max} - y_{min}) 并打印。
约束
- 1 \leq N \leq 10^5
- -10^8 \leq x_i,\ y_i \leq 10^8
- x_i 和 y_i 是整数。
- d_i is
R,L,U,或D.
输入
输入由标准输入按以下格式给出:
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}.
示例输入 1
2 0 3 D 3 0 L
示例输出 1
0
三秒后,两点将在原点相遇。所讨论的值将是 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