← 返回题目列表

Codeforces · 1468/G

G. 霍比特人

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

霍比特人弗罗多和山姆正带着至尊魔戒前往魔多。为了不被兽人发现,他们决定穿越山脉。

山地地形可以表示为具有 $$$n$$$ 点 $$$(x_i, y_i)$$$ 的折线,编号从 $$$1$$$ 到 $$$n$$$($$$x_i < x_{i + 1}$$$ for $$$1 \le i \le n - 1$$$)。霍比特人从点 $$$(x_1, y_1)$$$ 开始他们的旅程,应该到达点 $$$(x_n, y_n)$$$ 来完成他们的任务。

问题是有一座塔,塔上有索伦之眼,监视着他们。塔位于点 $$$(x_n, y_n)$$$ 处,高度为 $$$H$$$,因此眼睛位于点 $$$(x_n, y_n + H)$$$ 处。为了顺利完成任务,霍比特人必须在索伦之眼能看到他们的时候一直穿着斗篷,即。 e.当从眼睛到霍比特人有一条直线且未与浮雕相交时。

霍比特人身材矮小,因此他们的高度可以被认为小得可以忽略不计,但仍然是正数,因此当从索伦之眼到霍比特人的直线仅触及浮雕时,眼睛就可以看到他们。

索伦之眼在霍比特人处于左侧位置时看不到他们,但在霍比特人位于右侧位置时可以看到他们。

霍比特人不喜欢穿斗篷,所以他们只有在可以被眼睛发现的时候才穿斗篷。您的任务是计算霍比特人穿着斗篷时必须行走的总距离。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$H$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le H \le 10^4$$$) - 折线中的顶点数和塔的高度。

接下来的 $$$n$$$ 行包含两个整数 $$$x_i, y_i$$$ ($$$0 \le x_i \le 4 \cdot 10^5$$$; $$$0 \le y_i \le 10^4$$$) - 折线顶点的坐标。对于 $$$1 \le i \le n - 1$$$,保证 $$$x_i < x_{i + 1}$$$。

输出

打印一个实数——霍比特人穿着斗篷时必须行走的总距离。如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则您的答案将被视为正确 - 正式来说,如果您的答案是 $$$a$$$,而陪审团的答案是 $$$b$$$,则如果 $$$\dfrac{|a - b|}{\max(1, b)} \le 10^{-6}$$$,您的答案将被接受。

示例

输入 #1

6 10
10 40
20 10
25 30
30 15
50 15
65 30

输出 #1

70.4034587602

输入 #2

9 5
0 0
5 10
15 10
20 0
25 11
30 0
35 10
50 10
60 5

输出 #2

27.2787986124

输入 #3

2 10000
0 10000
400000 0

输出 #3

400124.9804748512