#P18313. Island Invasion

Island Invasion

Island Invasion

输入:标准输入
输出:标准输出

大岛和小岛是小海中相邻的两座岛屿。大岛国王为了满足自己的虚荣心,打算征服小岛。然而,小海上的风很强,船只又慢又轻,抵达小岛可能需要很长时间,甚至根本无法抵达。天气变化无常,风向很难预测,因此国王想提前计算不同风速条件下,从大岛抵达小岛所需的最短时间。

大岛和小岛分别由两个互不相交的凸多边形表示,顶点数分别为 nn 和 mm。你需要回答 qq 个询问。

每个询问给出风速向量 w⃗=(wx,wy)\vec w=(w_x,w_y),以及船只自身的最大速度 ss。船只可以从大岛上的任意一点出发,并任意选择自身的航行方向。如果船只的自身速度为 v⃗\vec v,则必须满足 ∣v⃗∣≤s|\vec v|\le s,而船只的实际速度为 v⃗+w⃗\vec v+\vec w。

对于每个询问,判断船只能否抵达小岛上的任意一点。如果可以,求出所需的最短时间。

输入格式

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

每个测试用例的第一行包含两个整数 n,mn,m。

接下来 nn 行,每行包含两个整数 x,yx,y,表示大岛的一个顶点。

再接下来 mm 行,每行包含两个整数 x,yx,y,表示小岛的一个顶点。每个多边形的顶点均按逆时针顺序给出。

随后一行包含整数 qq。

接下来 qq 行,每行包含三个整数 wx,wy,sw_x,w_y,s,表示一个询问。

输出格式

对于每个询问,输出一行。

  • 如果无法抵达小岛上的任何一点,输出 −1-1。
  • 否则,输出一个实数,表示所需的最短时间。

若你的答案为 aa,评测答案为 bb,则必须满足

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

注意原题公式使用严格小于。

数据范围

  • 1≤T≤11111\le T\le1111;
  • 3≤n,m≤1053\le n,m\le10^5;
  • 每个顶点坐标均满足 −109≤x,y≤109-10^9\le x,y\le10^9;
  • 1≤q≤2⋅1041\le q\le2\cdot10^4;
  • −109≤wx,wy≤109-10^9\le w_x,w_y\le10^9;
  • 0≤s≤1090\le s\le10^9;
  • 两个凸多边形互不相交,顶点按逆时针顺序给出;
  • 对同一个输入文件的全部测试用例,∑(n+m)≤2⋅105\sum(n+m)\le2\cdot10^5,∑q≤2⋅104\sum q\le2\cdot10^4;
  • 保证对于能够抵达小岛的询问,最短时间不超过 10910^9。

样例

输入

1
4 4
0 0
1 0
1 1
0 1
2 2
3 2
3 3
2 3
2
1 1 1
-1 -1 1

输出

0.5857860308
-1