阿尔卡迪在小镇游戏中达到了第n级,所以玛莎决定为他烤一个馅饼!当然,饼图的形状是凸n边形,即有n个顶点的多边形。
阿尔卡迪决定将馅饼沿直线切成面积相等的两部分,这样他就可以吃掉其中的一个,并将另一个给玛莎。这里有一个困难,因为阿尔卡迪已经在馅饼的某个点上放了一把刀,所以他现在必须通过穿过该点的直线来切馅饼。
帮助Arkady:找到一条穿过Arkady放刀的点的线,并将馅饼切成面积相等的两部分,或者确定这是不可能的。你的程序必须用同一个馅饼快速回答许多查询,但阿尔卡迪在不同的点上放了一把刀。
输入
第一行包含两个整数 n 和 q (3 ≤ n ≤ 104, 1 ≤ q ≤ 105) - 饼图中的顶点数和查询数。
接下来的 n 行按顺时针顺序描述多边形顶点。这些行的第 i 行包含两个整数 xi 和 yi (- 106 ≤ xi, yi ≤ 106)——第 i 个顶点的坐标。保证多边形是严格凸的,特别是三个顶点不能在同一直线上。
后面是一个空行。
q 行随后描述查询点。这些行的第 i 行包含两个整数 xi 和 yi (- 106 ≤ xi, yi ≤ 106)——Arkady 在第 i 个查询中放置刀的点的坐标。保证在每个查询中给定点严格位于多边形内部,特别是不在其边缘上。
输出
对于每个查询,打印单个整数 - 作为相应查询答案的线的极角(以弧度为单位)。角度应在[0;π]线段内,从OX轴方向按逆时针顺序测量角度。例如,OY 轴的极角为 $$\frac{1}{2}$$。如果该查询没有答案,则打印 -1。
如果有多个答案,请打印其中任何一个。如果各部分面积除以多边形总面积之差的绝对值不超过 10 - 4,则认为您的答案是正确的。换句话说,如果 a 和 b 是切割后零件的面积,那么当且仅当 $${ \frac { | } 时,你的答案才是正确的。 a - b | } { a + b } } \leq 1 0 ^ { - 4 }$$。
示例
输入 #1
3 1 0 0 0 3 3 0 1 1
输出 #1
2.67794504460098710000
输入 #2
5 3 6 5 6 3 5 0 0 0 0 5 5 4 3 3 5 2
输出 #2
0.60228734612690049000 1.27933953226473580000 2.85805511179015910000