P4636 [SHOI2011] Line Fitting

There are $n$ points $v_i(x_i, y_i)$ on the plane. Find the minimum possible value of $D(l)=\max_{1\le i\le n} dis(v_i, l)$, where the variable $l$ is a line on the plane, and $dis(v_i, l)$ denotes the distance between the line $l$ and the point $v_i$.

The first line contains a positive integer $n$. The next $n$ lines each contain a pair of integers $x_i, y_i$, separated by a space, representing the coordinates of the $n$ points in order. Here $|x_i|, |y_i| \le 10^8$, and no two points coincide.

Output a single line containing a real number, the minimum value of $D(l)$, rounded to two decimal places.

**Sample Explanation 1** In sample $1$, when the minimum is achieved, the line $l$ is $y=1$. **Sample Explanation 2** In sample $2$, the $6$ points and the line $l$ when $D(l)$ reaches its minimum are shown in the figure.  **Constraints and Notes** Test case $1$: $n=3$. Test cases $2 \sim 4$: $3 \le n \le 100$. Test cases $5 \sim 7$: $100 < n \le 100000$, and the input file is generated as follows: choose a line segment; each time, first pick a point uniformly at random on the segment, then take the lattice point closest to that point. Test cases $8 \sim 10$: $3 < n \le 100000$. Translated by ChatGPT 5