P2600 [ZJOI2008] Watchtower

The village head of village H, dadzhi, who is committed to building a nationally recognized harmonious small village, decides to build a watchtower in the village to improve public security. We abstract village H as a one-dimensional silhouette, as shown in the figure below.  We can describe the shape of village H by the upper contour polyline of a mountain $(x_1, y_1),(x_2, y_2),\cdots,(x_n, y_n)$, where $x_1 < x_2 < \cdots < x_n$. The watchtower can be built at any position within $[x_1, x_n]$, but it must satisfy that from the top of the watchtower one can see every point of village H. Clearly, the required height depends on where the watchtower is built. To save costs, village head dadzhi wants the tower’s height to be as small as possible. Please write a program to compute the minimum height of the tower.

The first line contains an integer $n$, denoting the number of vertices of the contour polyline. The second line contains $n$ integers, which are $x_1 \sim x_n$. The third line contains $n$ integers, which are $y_1 \sim y_n$.

Output a single real number, which is the minimum height of the tower, accurate to three digits after the decimal point.

For 60% of the testdata, $n \le 60$. For 100% of the testdata, $n \le 300$, and the absolute values of the input coordinates do not exceed $10^6$. Please be careful about floating-point errors. Translated by ChatGPT 5