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.

题目描述

$\texttt{Tohka}$ 暴走了！

暴走的 $\texttt{Tohka}$ 决定用自己的秘密武器把小 $H$ 劈成两半。好消息是小 $H$ 对 $\texttt{Tohka}$ 的武器提前有一定了解，他可以据此规划如何逃生。

具体来说，初始时小 $H$ 和 $\texttt{Tohka}$ 两个人都视作位于 $xOy$ 坐标系原点 $(0,0)$ 的质点。约定小 $H$ 开始逃跑的时刻为 $t=0$ 。

小 $H$ 已知 $\texttt{Tohka}$ 的武器由若干线段构成，但他不知道这些线段的具体形态，只知道所有线段端点都属于集合 $\{(0,0),(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\}$ ，其中 $\forall i, (x_i,y_i)\neq (0,0)$ 。

$\texttt{Tohka}$ 只能以 $1 ^\circ /s$ 的角速度绕着 $(0,0)$ 顺时针旋转这把武器，小 $H$ 也只能以 $1m/s$ 的速度沿 $x$ 轴正半轴逃跑。若某个 $t>0$ 的时刻，小 $H$ 与 $\texttt{Tohka}$ 武器上的任意一点（包括线段的端点）接触，小 $H$ 就视为被武器击中而未能逃生。

经过交涉，$\texttt{Tohka}$ 同意让小 $H$ 先跑 $k$ 秒（即 $\texttt{Tohka}$ 在 $t=k$ 秒时开始旋转武器），但是如果 $k$ 的值太大或者不是一个整数， $\texttt{Tohka}$ 很可能会意识到自己被耍了，从而直接把小 $H$ 扬了。

由于小 $H$ 过于恐慌无法思考，请你帮助他求出最坏情况下，小 $H$ 最少需要提前逃跑的整秒数 $k$ 。

输入格式

第一行输入一个正整数 $n\,\,(n\leq 2\times10^5)$ ，含义见题目描述。

接下来 $n$ 行，每行输入两个整数 $x_i,y_i$, $(|x_i|\leq 10^9,0 < y_i \leq 10^9)$ ，描述点的坐标，保证任意两点不重合。

为了避免浮点数误差，数据保证小 $H$ 最坏情况下提前逃跑恰好被击中的时间与 $k$ 的差值大于 $10^{-6}$ 。

输出格式

一行，输出一个非负整数 $k$ ，表示最少需要提前逃跑的整秒数。

输入输出样例 #1

输入 #1

3
1 1
-1 1
0 4

输出 #1

0

输入输出样例 #2

输入 #2

5
-5 13
19 2
2 16
-7 16
17 12

输出 #2

14

说明/提示

下图展示了样例 $1$ 中 $Tohka$ 武器的几种（并非全部）可能样式：

在以上三种情况下，$Tohka$ 的武器提前旋转 $(45-\sqrt{2})$ 秒才能击中小 $H$ 。可以证明不存在更坏的情况，因此小 $H$ 无需提前逃跑，$k=0$ .