Minimum Vertical Segment to Block All Lasers

On a 2D plane, there are n laser cannons. The i-th laser cannon is located at \( (-10^5, a_i) \) and aims at the target \( (10^5, b_i) \), forming a line segment connecting these two points. Little Ming wants to block all the laser beams by placing a vertical line segment (i.e. parallel to the y‐axis) such that one of its endpoints lies on the x‐axis. The vertical segment will block a laser beam if it intersects the laser beam segment. Find the minimum length of such a vertical segment that can block all the laser beams.

Explanation:

For a chosen vertical line at \( x=c \) (with \( c \in [-10^5,10^5] \) so that it intersects every beam) the intersection point of the i-th beam with this line is computed by linear interpolation: \[ f_i(c)=a_i+\frac{c+10^5}{2\cdot10^5}(b_i-a_i)=\frac{b_i-a_i}{2\cdot10^5}c+\frac{a_i+b_i}{2}. \]

The blocking segment must be vertical, with one endpoint on the x-axis (i.e. having y-coordinate 0) and the other endpoint at some y-value \( L \). This segment will cover all points between \( \min(0,L) \) and \( \max(0,L) \). In order to block a given beam, its intersection \( f_i(c) \) must lie in the interval between \( 0 \) and \( L \) (if \( L\ge0 \)) or between \( L \) and \( 0 \) (if \( L<0 \)). Thus, for each beam we need either:

• Case 1: \(L \ge 0\) and \(0 \le f_i(c) \le L\) for all \(i\); or
• Case 2: \(L < 0\) and \(L \le f_i(c) \le 0\) for all \(i\).

Your task is to choose an \( x=c \) (with \( c\in[-10^5,10^5] \)) and determine the corresponding minimum \( |L| \) such that either all \( f_i(c) \ge 0 \) (and \( L=\max_i f_i(c) \)) or all \( f_i(c) \le 0 \) (and \( L=\min_i f_i(c) \)), and minimize \( |L| \) overall.

Note: It might be more convenient to use binary search on the candidate length \( L \) to decide if there exists an \( x=c \) such that either all intersections fall in \([0,L]\) or in \([-L,0]\). The final answer should be printed with a precision of at least \( 10^{-6} \).

inputFormat

The first line contains an integer \( n \) \( (1 \le n \le 10^5) \), the number of laser cannons.

Each of the following \( n \) lines contains two integers \( a_i \) and \( b_i \) \( (-10^9 \le a_i, b_i \le 10^9) \) representing the y-coordinates of the launching point and the target point respectively.

outputFormat

Output a single real number representing the minimum length of the vertical segment required to block all lasers. The answer will be accepted if its absolute or relative error does not exceed \( 10^{-6} \).

sample

1
0 0

0.000000