Testing Your Geometry Template#10818
You are given distinct points P_1, P_2, \ldots, P_n on the coordinate plane, none of which lie on the -axis (-axis is the set of points whose coordinate is ).
Let be the set of all points on the -axis such that there exist two integers with 1 \le i < j \le n such that XP_i = XP_j. In other words, is the set of all points on the -axis which are equidistant from some two distinct points from P_1, \ldots, P_n.
Find the largest distance between any two points in (not necessarily distinct).
It's guaranteed that in all test cases, is nonempty and finite.
The first line contains a single integer (2 \le n \le 200000) — the number of points.
The -th of the next lines contains two integers x_i, y_i (-10^9 \le x_i, y_i \le 10^9, y_i \neq 0) — and coordinates of point P_i.
It's guaranteed that is nonempty and finite in all testcases.
Output a single number — the largest distance between any two points in (not necessarily distinct).
Your answer is considered correct if its absolute or relative error does not exceed 10^{-6}.
Formally, let your answer be , and the jury's answer be . Your answer is accepted if and only if \frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}.
Example 1
In the sample, S = \{(-7, 0), (0, 0), (7, 0)\}.
Note that if contains a single point, the answer will be .