← 返回题目列表

Codeforces · 799/G

G. 切馅饼

中文机器翻译题面 查看原题

阿尔卡迪在小镇游戏中达到了第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