Testing Your Geometry Template

You are given $n$ distinct points $P_1,P_2,\dots ,P_n$ on the coordinate plane, none of which lie on the $x$-axis ($x$-axis is the set of points whose $y$ coordinate is $0$).

Let $S$ be the set of all points $X$ on the $x$-axis such that there exist two integers $i,j$ with $1\le i<j\le n$ such that $X{P}_i=X{P}_j$. In other words, $S$ is the set of all points on the $x$-axis which are equidistant from some two distinct points from $P_1,\dots ,P_n$.

Find the largest distance between any two points in $S$ (not necessarily distinct).

It's guaranteed that in all test cases, $S$ is nonempty and finite.

Giriş verilənləri

The first line contains a single integer $n$ ($2\le n\le 200000$) — the number of points.

The $i$-th of the next $n$ lines contains two integers $x_i,y_i$ ($-10^9\le x_i,y_i\le 10^9$, $y_i\ne 0$) — $x$ and $y$ coordinates of point $P_i$.

It's guaranteed that $S$ is nonempty and finite in all testcases.

Çıxış verilənləri

Output a single number — the largest distance between any two points in $S$ (not necessarily distinct).

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a-b|}{\max (1,|b|)}\le 10^{-6}$.

Nümunələr

Qeyd

In the sample, $S=\{(-7,0),(0,0),(7,0)\}$.

Note that if $S$ contains a single point, the answer will be $0$.