#P17875. Dodge the Car
Dodge the Car
Dodge the Car
你准备横穿马路,但路上有一辆汽车正在行驶。
在平面直角坐标系中,一条宽为 的道路沿 轴方向无限延伸,占据条带 。你要从下侧边界 到达上侧边界 ,同时避开汽车。
汽车的车身用一个具有 个顶点的简单多边形表示。在时刻 ,这些顶点按逆时针顺序为
汽车以恒定的水平速度 行驶,因此在时刻 ,第 个顶点的位置为 。
你可以向任意方向移动,也可以等待,但速度不能超过 。等价地,对于任意两个时刻 ,你在这两个时刻的位置之间的欧几里得距离不能超过 。
在任何时刻,你都不能严格位于汽车车身的内部,但允许接触车身边界。
给定 个相互独立的询问。在第 个询问中,你在时刻 从 出发。求你安全到达直线 上任意一点所需的最短时间。
每个询问中,汽车都从相同的初始位置重新开始运动;不同询问之间互不影响。可以证明答案总是存在。
输入格式
第一行一个整数 ,表示测试用例数。
对于每个测试用例:
- 第一行四个整数 ,依次表示汽车的顶点数、道路宽度、汽车的水平速度,以及你的最大速度。
- 接下来 行,第 行两个整数 ,表示汽车在时刻0的第 个顶点。
- 接下来一行一个整数 ,表示询问数。
- 接下来 行,第 行一个整数 ,表示出发点 。
数据范围:
- ;
- ;
- ;
- ;
- ,;
- ;
- 。
顶点按逆时针边界顺序给出,并构成简单多边形:不相邻的边没有公共点,相邻的边只在共同端点相交,任意三个连续顶点不共线。不保证多边形为凸多边形。
所有测试用例的 之和不超过 , 之和也不超过 。
输出格式
对每个询问输出一行一个实数,表示安全到达 所需的最短时间。
若你的答案为 ,参考答案为 ,则当
时,答案被认为正确。
样例
3
6 10 1 3
-3 3
3 3
3 5
1 5
1 7
-3 7
3
0
6
-6
4 20 5 1
-12 2
2 2
2 10
-2 10
2
0
-12
4 8 2 5
-5 0
5 0
5 8
-5 8
2
-3
3
3.504497942940
3.333333333333
3.333333333333
20.211324865405
20.000000000000
1.885714285714
2.412409788555