← 返回题目列表

AtCoder · icpc2013summer_day3_k

J. 库库鲁库鲁林

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

Herim呈现为二维平面上长度2L的线段形状。
Heririn的周围存在着几条线段形状的障碍物。

Heririn接触到障碍物时会损失体力。
完美主义者Heririn决定毫发无伤地到达终点。

Herim可以进行以下行动。

  • 平行移動

  • 以表示Heririn的线段的中点为中心,逆时针旋转恰好 180 / r 度

不过,二维平面将向上方向取y轴。

Heririn的周围有两个点S、G。
开始时Heririn的中心位于点S,且x处于与轴平行的状态。

Heririn擅长平行移动,但不擅长旋转。
你的任务是求出在将Heririn的中心从点S移动到点G之前所需的最少旋转行动次数。
如果无法移动,也请检测出这一情况。

不过,请注意以下事项。

  • Heririn不能在移动的同时旋转。

  • 如果Heririn在旋转过程中可能撞到障碍物,则不能进行旋转。

  • 障碍物之间可能相互交叉。

  • 将线段视为具有足够小的有限厚度。请参见最后一个样例。

输入

输入按以下格式给出。

L r
sx sy
gx gy
n
x11 y11 x12 y12
...
xn1 yn1 xn2 yn2

L表示周长的一半。 r用于确定旋转角度。 (sx, sy)是点 S 的(gx, gy)是点 G 的坐标。 n表示障碍物的数量。 (xi1, yi1)和 按字典顺序比较(xi2, yi2)是 您也可以写i是表示第 个障碍物的线段的端点。

约束

输入满足以下约束。

  • 1 \leq n \leq 30

  • 2\leq r \leq 11

  • 1 \leq L \leq 105

  • 输入中所含坐标的各个分量的绝对值为105以下

  • 输入中所含的数值全部为整数

  • i = 1, ..., n关于 (xi1, yi1) \neq (xi2, yi2)

  • 将 Heririn 放置在起点处,并使其处于沿 x 轴水平的状态时,与障碍物之间的(线段与线段之间的)距离为 10-3 大于

  • 将表示障碍物的线段的端点向两个方向各延长 10-3 即使将其延长或缩短,也不会改变答案

  • L该值应乘以 10-3 即使将其增加或减少,也不会改变答案

  • 障碍线段 如果我们写li,1 \leq i \leq j \leq n并且,li和 按字典顺序比较lj的距离是2L一组使得(i, j)最多 100 件

  • 目标点不在任何障碍物上。

输出

在一行中输出从起点移动到目标点所需的最小旋转圈数。 如果无法移动它,请在一行上打印 -1。

示例输入 1

1 2
3 3
2 -1
4
1 0 1 5
0 1 4 1
0 4 6 4
5 0 5 5

样本输入 1 的输出

1
  • 通过将 Helirin 旋转 90 度,就可以通过间隙。

示例输入 2

1 2
3 3
2 -1
4
1 0 1 5
0 1 6 1
0 4 6 4
5 0 5 5

样本输入 2 的输出

-1
  • Helirin被完全包围,无法移动到球门。

示例输入 3

1 4
3 3
7 0
5
1 0 1 5
0 1 6 1
0 4 6 4
8 0 2 5
6 0 4 2

样本输入 3 的输出

3
  • 要沿着对角线路径移动,您必须逆时针旋转三圈。

示例输入 4

2 2
4 2
4 5
5
1 5 2 0
0 4 3 4
0 1 8 1
7 0 7 5
8 4 5 4

样本输入 4 的输出

-1
  • Helirin无法与障碍物直接接触,因此无法在间隙中旋转并移动到球门。