← 返回题目列表

Codeforces · 1381/E

E. 折纸

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

在一道难看的几何题上 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$$$: