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无法与障碍物直接接触,因此无法在间隙中旋转并移动到球门。