bzoj#P3116. 登顶计划

登顶计划

题目描述

二维平面上的山脉由一系列顶点确定:(x1,y1),(x2,y2)(xn,yn)(x_1,y_1),(x_2,y_2)\cdots (x_n,y_n)。相邻的两个顶点之间由线段相连(保证 xix_i 严格递增),这样就构成了一座连绵的山脉,每个点的 yy 值代表了该点的高度。如下图所示: pic1.jpg

我们定义山脉的内部为顶点之间的折线与x轴的所夹部分(不包括顶点之间的折线)。如果顶点 AA 与顶点 BB 之间的连线段没有穿过山脉的内部,则我们称顶点 AA 能看见顶点 BB(或 BB 能看见 AA)。 现在pty从某个顶点出发,想要登到山脉的顶峰(最高点),他只能在顶点之间的折线上行走。经过思考,他将采取如下的一种登山方式:

1.站在出发点,向左右看去,如果此时能够看到的最高山峰在左侧,则向左侧走去,否则向右侧走去。 2.在行走的同时,pty 仍然观察着此时左右的最高山峰,一旦发现一座比之前看到的都要高的山峰,他将向此时的最高峰走去。 3.如果存在某个时刻,pty 所站立的位置比左右能看到的最高峰都要高,则他到达了山脉的顶峰,此时他的爬山过程结束。

pty 想知道,采取如上的策略,从每个顶点出发,到达最高点的路程分别是多少?(平面中两点的距离等于它们之间连线段的长度)

输入格式

第一行一个整数 nn,表示山脉顶点个数。 接下来 nn行,第 ii 行两个整数 xi,yix_i,y_i,表示第 ii个顶点的坐标。 保证 xix_i 严格递增,yiy_i 互不相同(y1,yny_1,y_n 除外),xi,yix_i,y_i 都为非负整数。保证 y1,yny_1,y_n 的值为 00

输出格式

输出共 nn 行:每行一个实数 第 ii 行的实数表示从第 ii 个顶点出发,到达最高点的路程。 如果输出与标准输出的误差不超过 10210^{-2},则该测试点得满分,否则得 00 分。

6
0 0
1 6
2 4
3 1
5 5
6 0
6.08
0.00
2.24
6.52
9.87
14.97

样例说明

AA 点出发:ABA\to BBB 点出发:BBCC 点出发:CBC\to BDD 点出发:DGDCBD\to G\to D\to C\to BEE 点出发:EDCBE\to D\to C\to BFF 点出发:FEDCBF\to E\to D\to C\to B;从 DD 点出发时,看到的最高点是 EE,当步行至 GG 点时,发现更高点 BB,转向后一直步行向 BB 点。从其它点出发后都不需要转向。 pic2.jpg

数据规模与约定

所有的数据满足 xi,yi105x_i,y_i\le 10^5

1-4 的测试点 满足 n20n \le 20

5-8 的测试点,满足 n70n \le 70

9-10 的测试点,满足 n105n \le 10^5且每个顶点都能直接看到最高点。

11-14 的测试点,满足 n3×104 n\le 3 \times 10^4。

15-20 的测试点,满足 n105n \le 10^5。

题目来源

PTY 提供