← 返回题目列表

Codeforces · 182/A

A. 战场

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

瓦夏在大学落后,上了战场。只是开玩笑!他只是在玩电脑游戏。场地是一个平坦的平台,上面挖了n条沟渠。沟槽是平行于坐标轴的平面上的片段。没有两条战壕相交。

距离瓦西亚很远的地方有一个巨大的敌方激光。激光充电 1 秒,然后连续发射 b 秒。然后,它再次充电一秒钟。然后再次连续射击 b 秒,依此类推。瓦夏知道数字 a 和 b。他还知道,当激光射击时,瓦夏一定在战壕中,但当激光充电时,瓦夏可以安全地在场地内移动。最主要的是在射击前有时间躲进战壕里。如果瓦夏恰好在激光开始射击的那一刻到达战壕,我们相信瓦夏成功地躲了起来。巧合的是,任何沟槽的长度(以米为单位)在数值上都不超过 b。

最初,Vasya 在 A 点。他需要到达 B 点。Vasya 以每秒 1 米的速度向任一方向移动。您可以在任何一点进出战壕。进出战壕并不需要时间。也可以在战壕中移动而不离开它。

如果激光刚开始充电,Vasya 从 A 点到 B 点需要的最短时间是多少?如果 Vasya 无法从 A 点到达 B 点,则打印 -1。如果瓦夏在激光开始发射的那一刻到达了B点,则认为瓦夏成功到达了B点。

输入

第一行包含两个空格分隔的整数:a和b (1 ≤ a, b ≤ 1000),——充电时长和拍摄时长,以秒为单位。

第二行包含四个空格分隔的整数:Ax, Ay, Bx, By (- 104 ≤ Ax, Ay, Bx, By ≤ 104) — А 和 B 点的坐标。保证 A 点和 B 点不属于任何沟槽。

第三行包含一个整数:n (1 ≤ n ≤ 1000), — 沟槽数量。

以下 n 行中的每一行都包含四个空格分隔的整数:x1, y1, x2, y2 (- 104 ≤ xi, yi ≤ 104) — 相应沟槽末端的坐标。

所有坐标均以米为单位。对于任何沟槽,保证 x1 = x2 或 y1 = y2。没有两条战壕相交。任何沟槽的长度(以米为单位)在数值上不超过 b。

输出

如果 Vasya 可以从 A 点到达 B 点,请打印他所需的最短时间。否则,打印数字-1。

如果绝对或相对误差不超过 10 - 4,则答案将被视为正确

示例

输入 #1

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

输出 #1

19.0000000000

输入 #2

5 10
0 0 10 10
1
5 0 5 9

输出 #2

-1