#P18516. Map 2

Map 2

Map 2

Noah 玩过一款角色扮演游戏:他需要踩着一头巨大驼鹿的背,寻找一处秘密造船厂。游戏的寻路系统十分糟糕,因此他总在想,如果游戏有一个合适的地图导航系统,会是什么样子。

游戏地图可以表示为一个简单多边形 (M)。Noah 不能走出 (M),但可以沿边界行走。造船厂位于 (M) 内部或边界上的固定点 (p)。一个合适的导航系统应该始终显示当前位置到 (p) 的最短路线。

给定 (M)、(p) 以及 Noah 的若干位置 (a_1,\ldots,a_Q),求每个 (a_i) 到 (p) 的、完全位于多边形闭域内的最短路径长度。

输入格式

一个输入文件包含多组测试。第一行是整数 (T)((1\le T\le5000)),表示测试组数。

每组测试首先给出整数 (n)((3\le n\le5000)),表示多边形顶点数。接下来 (n) 行依次给出顶点,顺序为逆时针。下一行给出固定点 (p),下一行给出整数 (Q)((1\le Q\le5000)),接下来 (Q) 行依次给出询问点 (a_i)。

每个点以空格分隔的两个整数坐标 (x,y) 表示,满足 (|x|,|y|\le2000)。

保证输入中的所有点都位于 (M) 内部或边界上。保证 (M) 是简单多边形:顶点互不相同;任意两条边不会相交或接触,唯一例外是相邻两条边在其公共端点处接触。原题没有保证连续三个顶点不共线。

一个输入文件内,所有测试的 (n) 之和不超过 (5000),所有测试的 (Q) 之和也不超过 (5000)。这两个总量限制分别计算。

输出格式

按测试顺序,每组测试输出 (Q) 行。第 (i) 行输出 (a_i) 到 (p) 的最短路径长度。

若答案的绝对误差或相对误差不超过 (10^{-6}),则认为正确。点允许在边界或顶点处,询问点也允许与 (p) 相同。

样例

输入:

1
6
0 5
4 4
4 -4
0 -5
6 -4
6 4
0 5
6
4 4
4 -4
6 4
6 -4
0 -5
5 -3

输出:

4.123105625618
12.123105625618
6.082762530298
12.369316876853
16.246211251235
11.194173437483

原题样例示意图如下,(p) 为造船厂,红点为六个询问位置:

原题样例多边形、固定点及询问点