CF589M Taxi in Berland
题目背景
波利卡普来到柏林首都参加一个重要会议。为了不迟到,他叫了一辆出租车,让司机尽快把他从火车站送到将举办会议的大楼,不过会议几分钟后就要开始了。
题目描述
首都柏林是一个矩形区域,宽度为 $w$ ,长度为 $l$ 。从平面上看,该地被视为一个矩形,最左的底角在点 $(0,0)$ ,最右的顶角在 $(w,l)$ 。柏林首都的道路是平行于坐标轴的连续垂直和水平段。有 $w+1$ 条垂直道路和 $l+1$ 条水平道路。第二条垂直道路 $i$ $(0 \le i \le w)$的端点坐标在点 $(i,0)$ 和 $(i,l)$ 中。第 $j(0 \le j \le l)$ 条水平道路的端点坐标位于点 $(0,j)$ 和 $(w,j)$ 中。因此,具有整数坐标的矩形域内的每个点都是一个十字路口。
火车站位于田野的尽头(用整数坐标表示为) $(x1,y1)$ 处。波利卡普将在此点乘坐出租车。主要会议将在该地点(用整数坐标表示为) $(x2,y2)$ 的一栋建筑内举行。
首都柏林的汽车只能通过公路行驶,也就是说,从每个十字路口,汽车都可以向上左下右四个方向行驶到附近的十字路口(汽车在行驶过程中不能离开场地边界)。
为波利卡普服务的出租车可以加速和减速,但加速度绝对值不超过 $a$ ,出租车的最大速度为 $ v_{max} $ 。出租车可以转弯(甚至旋转以反转方向),并且不会降低速度。
这些命令在首都柏林都会严格遵守,在城市的十字路口有配备测速雷达的 $n$ 辆警车。柏林首都允许的最高速度是 $ v_{p} $ 因此,如果警察在十字路口,那么出租车司机不会以大于 $v{p}$ 的速度通过这个十字路口(位于十字路口的警察 $(x{i},y{i})$ 测量汽车通过这个十字路口时的速度)。但反之,因为没有被捕的风险,出租车司机同意在城市的任何其他地方以任何速度行驶。
出租车从点 $(x_{1},y_{1})$ 开始,速度为零。波利卡普非常害怕迟到,以至于他同意在出租车到达$(x_{2},y_{2})$的时候跳下车。因此,出租车可以以不超过$v_{max}$的任何速度到达路径的终点。
保证没有两名警察处于同一位置。在 $(x_{1},y_{1})$ 和 $(x_{2},y_{2})$ 点没有警察。点 $(x_{1},y_{1})$ 和 $(x_{2},y_{2})$ 是不同的。
你必须找到出租车司机到达目的地的最短时间,且不会因为超速(速度超过 $v_{p}$)被警察逮到。
输入格式
输入的第一行包含六个数字 $w、l、n、a、v_{max}、v_{p}$ ( $1 \le w,l \le 100,0 \le n \le 100,$ $0.01 \le a \le 5.00,1 \le v_{max},v_{p} \le 100$ )。所有给定的数字都是整数,除了加速度$a$,它是一个两位小数。
输入的第二行包含四个整数$X_{1},Y_{1},X_{2},Y_{2}$ $(0 \le X_{1},X_{2} \le W,0 \le Y_{1},Y_{2} \le L)$ 其中 $(X_{1},Y_{1})$ 是起点(火车站)。 $(X_{2},Y_{2})$ 是终点(会议将举行的大楼)。
以下$n$行包含两个整数$x_{i},y_{i}(0 \le x_{i} \le w,0 \le y_{i} \le l)$——警察所在的十字路口坐标。
保证没有两名警察处于同一位置。在$(x_{1},y_{1})$和$(x_{2},y_{2})$点没有警察。点$(x_{1},y_{1})$和$(x_{2},y_{2})$是不同的。
输出格式
输出应包含一个浮点数,即出租车司机将波利卡普从火车站送到会议大楼所需的最短时间。答案的误差不应超过$10^{-6}$。