题目描述

二维平面上的山脉由一系列顶点确定：$(x_1,y_1),(x_2,y_2)\cdots (x_n,y_n)$。相邻的两个顶点之间由线段相连（保证 $x_i$ 严格递增），这样就构成了一座连绵的山脉，每个点的 $y$ 值代表了该点的高度。如下图所示：

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

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

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

输入格式

第一行一个整数 $n$，表示山脉顶点个数。 接下来 $n$行，第 $i$ 行两个整数 $x_i,y_i$，表示第 $i$个顶点的坐标。 保证 $x_i$ 严格递增，$y_i$ 互不相同（$y_1,y_n$ 除外），$x_i,y_i$ 都为非负整数。保证 $y_1,y_n$ 的值为 $0$。

输出格式

输出共 $n$ 行：每行一个实数 第 $i$ 行的实数表示从第 $i$ 个顶点出发，到达最高点的路程。 如果输出与标准输出的误差不超过 $10^{-2}$，则该测试点得满分，否则得 $0$ 分。

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

样例说明

$A$ 点出发：$A\to B$；$B$ 点出发：$B$；$C$ 点出发：$C\to B$；$D$ 点出发：$D\to G\to D\to C\to B$；$E$ 点出发：$E\to D\to C\to B$；$F$ 点出发：$F\to E\to D\to C\to B$；从 $D$ 点出发时，看到的最高点是 $E$，当步行至 $G$ 点时，发现更高点 $B$，转向后一直步行向 $B$ 点。从其它点出发后都不需要转向。

数据规模与约定

所有的数据满足 $x_i,y_i\le 10^5$。

1-4 的测试点 满足 $n \le 20$。

5-8 的测试点，满足 $n \le 70$。

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

11-14 的测试点，满足 $n\le 3 \times 10^4。$

15-20 的测试点，满足 $n \le 10^5。$

题目来源

PTY 提供