在一道难看的几何题上 13 次超出时限的判决让你灰心丧气后,你决定为艺术和手工艺放松一下。
有一张纸,形状是一个简单的多边形,有 $$$n$$$ 个顶点。多边形可能是非凸的,但我们都知道,正确的折纸具有以下性质:任何水平线最多与多边形边界相交于两个点。
如果沿垂直线 $$$x=f$$$ 折叠纸张,所得形状的面积是多少?折叠时,线条左侧的纸张部分对称地反映在右侧。
您的任务是回答 $$$q$$$ 值 $$$f_1,\ldots,f_q$$$ 的独立查询。
输入
第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$3\le n\le 10^5, 1\le q\le 10^5$$$) — 分别是多边形顶点和查询的数量。
接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$、$$$y_i$$$ ($$$|x_i|, |y_i|\le 10^5$$$) — 多边形第 $$$i$$$ 点的坐标。多边形有一条连接输入中每对相邻点的边,以及 $$$(x_1,y_1)$$$ 和 $$$(x_n,y_n)$$$ 之间的边。保证多边形是非退化的,并且任何水平线最多在两个点与多边形的边界相交。特别是,没有边界边缘是严格水平的。两个相邻边可以共线。
接下来的 $$$q$$$ 行包含一个整数 $$$f_i$$$ ($$$\min\limits_{j=1}^n(x_j)< f_i< \max\limits_{j=1}^n(x_j)$$$) — 第 $$$i$$$ 折叠查询的 $$$x$$$ 坐标。保证所有 $$$f_i$$$ 都是不同的。
输出
对于每个查询,如果沿 $$$x=f_i$$$ 线折叠纸张,则输出纸张的面积 $$$A_i$$$。
如果您的答案的绝对或相对误差不超过 $$$10^{-4}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$ 时,您的答案才会被接受。
示例
输入 #1
4 7 0 10 10 0 0 -10 -10 0 -9 -5 -1 0 1 5 9
输出 #1
199.0000000000 175.0000000000 119.0000000000 100.0000000000 119.0000000000 175.0000000000 199.0000000000
输入 #2
4 1 0 0 0 2 2 4 2 2 1
输出 #2
3.0000000000
输入 #3
9 4 0 -3 2 -2 -1 -1 0 4 2 5 1 6 -2 3 -1 1 -3 0 0 -2 -1 1
输出 #3
11.1250000000 11.7500000000 10.3446969697 11.3333333333
注意
第一个测试,折叠 $$$f=-5$$$:
第二个测试,折叠 $$$f=1$$$:
第三个测试,折叠 $$$f=-1$$$: