#P17875. Dodge the Car

Dodge the Car

Dodge the Car

你准备横穿马路,但路上有一辆汽车正在行驶。

在平面直角坐标系中,一条宽为 ww 的道路沿 xx 轴方向无限延伸,占据条带 0≤y≤w0\le y\le w。你要从下侧边界 y=0y=0 到达上侧边界 y=wy=w,同时避开汽车。

汽车的车身用一个具有 nn 个顶点的简单多边形表示。在时刻 t=0t=0,这些顶点按逆时针顺序为

(x1,y1),(x2,y2),…,(xn,yn).(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n).

汽车以恒定的水平速度 uu 行驶,因此在时刻 tt,第 ii 个顶点的位置为 (xi+ut,yi)(x_i+ut,y_i)。

你可以向任意方向移动,也可以等待,但速度不能超过 vv。等价地,对于任意两个时刻 0≤t1≤t20\le t_1\le t_2,你在这两个时刻的位置之间的欧几里得距离不能超过 v(t2−t1)v(t_2-t_1)。

在任何时刻,你都不能严格位于汽车车身的内部,但允许接触车身边界。

给定 qq 个相互独立的询问。在第 jj 个询问中,你在时刻 t=0t=0 从 (sj,0)(s_j,0) 出发。求你安全到达直线 y=wy=w 上任意一点所需的最短时间。

每个询问中,汽车都从相同的初始位置重新开始运动;不同询问之间互不影响。可以证明答案总是存在。

输入格式

第一行一个整数 TT,表示测试用例数。

对于每个测试用例:

  • 第一行四个整数 n,w,u,vn,w,u,v,依次表示汽车的顶点数、道路宽度、汽车的水平速度,以及你的最大速度。
  • 接下来 nn 行,第 ii 行两个整数 xi,yix_i,y_i,表示汽车在时刻0的第 ii 个顶点。
  • 接下来一行一个整数 qq,表示询问数。
  • 接下来 qq 行,第 jj 行一个整数 sjs_j,表示出发点 (sj,0)(s_j,0)。

数据范围:

  • 1≤T≤5×1041\le T\le5\times10^4;
  • 3≤n≤5×1053\le n\le5\times10^5;
  • 1≤w,v≤1091\le w,v\le10^9;
  • −109≤u≤109-10^9\le u\le10^9;
  • −109≤xi≤109-10^9\le x_i\le10^9,0≤yi≤w0\le y_i\le w;
  • 1≤q≤5×1051\le q\le5\times10^5;
  • −109≤sj≤109-10^9\le s_j\le10^9。

顶点按逆时针边界顺序给出,并构成简单多边形:不相邻的边没有公共点,相邻的边只在共同端点相交,任意三个连续顶点不共线。不保证多边形为凸多边形。

所有测试用例的 nn 之和不超过 5×1055\times10^5,qq 之和也不超过 5×1055\times10^5。

输出格式

对每个询问输出一行一个实数,表示安全到达 y=wy=w 所需的最短时间。

若你的答案为 aa,参考答案为 bb,则当

∣a−b∣max⁡(1,∣b∣)≤10−6\frac{|a-b|}{\max(1,|b|)}\le10^{-6}

时,答案被认为正确。

样例

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