16361번 - LED 다국어

A Light-Emitting Diode (LED) is a semiconductor light source, which emits light when an electric current of voltage higher than a threshhold is applied to its leads. ACM R&D recently reported that they have succesfully developed a new LED, namely, ACMOLED. An ACMOLED has a special behavior that the intensity of light emitted from it changes in two steps as the voltage of the electric current increases, as depicted in the graph below.

As shown, an ACMOLED is not activated in the voltage range from 0 to V₁, while it emits light with intensity L₁ ≥ 0 when the voltage reaches the first threshold V₁ and light with intensity L₂ ≥ L₁ when the voltage reaches the x threshold V₂. More specifically, if F(v) is the function that maps voltage v to the intensity of light emitted from an ACMOLED, then for four real numbers L₁, L₂, V₁, and V₂ with 0 ≤ L₁ ≤ L₂ and 0 < V₁ < V₂, we have

F(v) = 0 (if 0 ≤ v < V₁), L₁ (if V₁ ≤ v < V₂), L₂ (if v ≥ V₂)

The very issue now is that ACM R&D still does not know the exact values of two threshold voltage values V₁ and V₂ and the two intensity values L₁ and L₂ as well. Researchers in ACM R&D plan to estimate these four values for ACMOLEDs by repeated experiments.

Experiments are performed by applying current of a specific voltage and observing the intensity of light emitted from an ACMOLED. After n repeated experiments with different voltage values, obtained are the data of n tuples (v₁, l₁), (v₂, l₂), ..., (v_n, l_n), where l_i is the observed intensity for voltage v_i. Due to the impreciseness of the observing device and other reasons, the experimental data are not accurate and may contain some error. Nonetheless, they want to find a best estimated intensity function F(v) that minimizes the following error function:

error(F) = max_1≤i≤n |l_i - F(v_i)|

where |x| denotes the absolute value of a real number x.

For a given data of n tuples, write a program that finds an estimated intensity function F that minimizes the above error function and outputs the value of error(F).

Your program is to read from standard input. The input starts with a line containing an integer n (1 ≤ n ≤ 300,000), where n is the number of tuples (v_i, l_i) in the experimental data. In the following n lines, each line contains two integers, which range inclusively from 0 to 10⁹, representing v_i and l_i in each tuple (v_i, l_i) of the experimental data. Note that you may assume that there are no two tuples (v_i, l_i) and (v_j, l_j) in the input such that 1 ≤ i < j ≤ n and v_i = v_j.

Your program is to write to standard output. Print exactly one line consisting of one real number, rounded to the first decimal place, which represents the minimum value of error(F).