Testing Your Geometry Template
Testing Your Geometry Template
You are given n distinct points P_1, P_2, \ldots, 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 XP_i = XP_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, \ldots, 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.
Input data
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 \neq 0) — x and y coordinates of point P_i.
It's guaranteed that S is nonempty and finite in all testcases.
Output data
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}.
Examples
3 0 1 -2 5 2 5
14.0000000000
Note
In the sample, S = \{(-7, 0), (0, 0), (7, 0)\}.
Note that if S contains a single point, the answer will be 0.