You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一座山脉，这座山脉连绵起伏。

我们考虑它在一个平面直角坐标系上，由 $n$ 个首尾相接的线段组成。首尾端点及中间的连接点称作“拐点”。拐点的坐标是 $(x_i,y_i)$，并且都在原点、正半轴或第一象限里。

现在你需要装一盏灯，它可以在任何位置，也就是说，它可以漂浮。

但是它的坐标 $(p,q)$ 要保证 $p,q\ge0$，即坐标在原点、正半轴或第一象限里，同时也要保证在山脉上方。

同时要求这盏灯要照到所有拐点。

换句话说，$(p,q)$ 到 $(x_i,y_i)$ 的线段不能穿过山脉（即所有线段）。特别地，擦着边是允许的（具体见样例）。

求所有可以放灯的坐标中，$q$（即灯的纵坐标）的最小值。

输入格式

一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x_i,y_i$。

输出格式

一个 $4$ 位小数，为 $\min\{q\}$。你的输出的答案与标准答案误差不超过 $10^{-3}$ 即算作通过。

6
0 0
2 0
4 3
6 3
7 0
10 0

5.0000

样例解释

黄色点就是灯。可以证明没有更小的 $q$ 了。

数据范围

对于 $100\%$ 的数据，$1\le n\le10^5,0 \le x_i,y_i \le 10^6,0\le q\le10^{18}$。

保证 $x_i$ 单调上升。