← 返回题目列表

AtCoder · icpc2015summer_day4_b

B. 向量场

中文机器翻译题面 查看原题

问题陈述

20015年,JAG(Jagan Acceleration Group)成功发明了一种名为“Force Point”的新型加速器,用于二维$xy$平面上的质子碰撞实验。 如果质子接触力点,它会加速到其速度的两倍,并且其运动方向会发生转向。 质子可以通过力场以四种方式转向:平行于 $x$ 轴或 $y$ 轴的正方向或负方向。质子转向的方向由力点的类型决定。 力点只能加速质子一次,因为力点在加速后立即消失。 在二维平面上生成许多力点(称为 2D 力点场),使我们能够通过使用 2D 力点场中的力点顺序加速质子,将质子加速到目标速度。

Force Point 生成方法仍在试验中,JAG 具有以下技术限制:

  • JAG 无法生成具有指定位置和类型的力点。
  • 将质子放入 2D 力点场后,JAG 无法生成力点。
  • JAG 无法移动原力点。
  • JAG 无法改变质子的方向,除非通过力点的效果。
  • JAG 只能将一个质子用于 2D 力点场。
  • JAG 可以将质子以任意方向移动,速度为 1,置于 2D 力点场中的任意位置。

为了达到质子的最大速度,JAG的工程师必须在仔细观察生成的二维力点场后,选择质子的最佳初始位置和最佳初始方向,以便质子被尽可能多的力点加速。

通过观察生成的2D力点场,已知生成的力点的数量为$n$。第 $i$ 个点的位置 ($x_i$, $y_i$) 和方向转向类型 $d_i$ 也是已知的。 您的任务是编写一个程序,通过 JAG 最佳放置质子时在给定 2D 力点场上的加速度来计算质子的最大速度。


输入

输入由单个测试用例组成,该测试用例按以下格式描述 2D 力点字段。

$n$
$x_1$ $y_1$ $d_1$
...
$x_n$ $y_n$ $d_n$

第一行包含一个整数 $n$ ($1\le n\le 3{,}000$),它是 2D 力点场上力点的数量。接下来的 $n$ 行中的每一行都包含两个整数 $x_i$ 和 $y_i$ ($|x_i|, |y_i| \le 10^9$) 和一个字符 $d_i$ ($d_i$ 是 '>'、'v'、'<' 或 '^' 之一)。 $x_i$和$y_i$表示第$i$个力点的坐标,$d_i$是第$i$个力点的方向转向类型。类型为 '>' 的力点将质子的方向更改为 $x$ 轴的正方向,'v' 表示 $y$ 轴的正方向,'<' 表示 $x$ 轴的负方向,'^' 表示 $y$ 轴的负方向。您可以假设任意两个力点不是在同一坐标上生成的。

输出

显示包含整数 $\log_2 v_{\mathrm{max}}$ 的行,其中 $v_{\mathrm{max}}$ 是质子可能的最快速度。


示例输入 1

9
0 0 v
1 0 >
2 0 <
0 1 >
1 1 v
2 1 v
0 2 ^
1 2 ^
2 2 <

样本输入 1 的输出

9

输入如下图所示。 如果将质子放在 $(1, 1)$ 处,所有力点都会消失。

v><
>vv
^^<

示例输入 2

9
0 0 ^
1 0 ^
2 0 ^
0 1 <
1 1 ^
2 1 >
0 2 v
1 2 v
2 2 v

样本输入 2 的输出

2