#P18313. Island Invasion
Island Invasion
Island Invasion
输入:标准输入
输出:标准输出
大岛和小岛是小海中相邻的两座岛屿。大岛国王为了满足自己的虚荣心,打算征服小岛。然而,小海上的风很强,船只又慢又轻,抵达小岛可能需要很长时间,甚至根本无法抵达。天气变化无常,风向很难预测,因此国王想提前计算不同风速条件下,从大岛抵达小岛所需的最短时间。
大岛和小岛分别由两个互不相交的凸多边形表示,顶点数分别为 和 。你需要回答 个询问。
每个询问给出风速向量 ,以及船只自身的最大速度 。船只可以从大岛上的任意一点出发,并任意选择自身的航行方向。如果船只的自身速度为 ,则必须满足 ,而船只的实际速度为 。
对于每个询问,判断船只能否抵达小岛上的任意一点。如果可以,求出所需的最短时间。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例的第一行包含两个整数 。
接下来 行,每行包含两个整数 ,表示大岛的一个顶点。
再接下来 行,每行包含两个整数 ,表示小岛的一个顶点。每个多边形的顶点均按逆时针顺序给出。
随后一行包含整数 。
接下来 行,每行包含三个整数 ,表示一个询问。
输出格式
对于每个询问,输出一行。
- 如果无法抵达小岛上的任何一点,输出 。
- 否则,输出一个实数,表示所需的最短时间。
若你的答案为 ,评测答案为 ,则必须满足
注意原题公式使用严格小于。
数据范围
- ;
- ;
- 每个顶点坐标均满足 ;
- ;
- ;
- ;
- 两个凸多边形互不相交,顶点按逆时针顺序给出;
- 对同一个输入文件的全部测试用例,,;
- 保证对于能够抵达小岛的询问,最短时间不超过 。
样例
输入
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